14 citations · 21 across the 10 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.CC2018
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
Iyad Kanj, Christian Komusiewicz, Manuel Sorge +1
A fundamental graph problem is to recognize whether the vertex set of a graph can be bipartitioned into sets and such that and satisfy properties an…
cs.DS2018★ 2 cited
Subexponential-time Algorithms for Maximum Independent Set in -free and Broom-free Graphs
Gábor Bacsó, Daniel Lokshtanov, Dániel Marx +3
In algorithmic graph theory, a classic open question is to determine the complexity of the Maximum Independent Set problem on -free graphs, that is, on graphs not containing a…
cs.DS2018
Disconnected Cuts in Claw-free Graphs
Barnaby Martin, Daniel Paulusma, Erik Jan van Leeuwen
A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The decision problem whether a graph has a disconnected cut is called Disc…