TY - GEN
T1 - Fully decomposable split graphs
AU - Broersma, H.J.
AU - Kratsch, D.
AU - Woeginger, G.J.
PY - 2009
Y1 - 2009
N2 - We discuss various questions around partitioning a split graph into connected parts. Our main result is a polynomial time algorithm that decides whether a given split graph is fully decomposable, i.e., whether it can be partitioned into connected parts of order a 1,a 2,...,a k for every a 1,a 2,...,a k summing up to the order of the graph. In contrast, we show that the decision problem whether a given split graph can be partitioned into connected parts of order a 1,a 2,...,a k for a given partition a 1,a 2,...,a k of the order of the graph, is NP-hard.
AB - We discuss various questions around partitioning a split graph into connected parts. Our main result is a polynomial time algorithm that decides whether a given split graph is fully decomposable, i.e., whether it can be partitioned into connected parts of order a 1,a 2,...,a k for every a 1,a 2,...,a k summing up to the order of the graph. In contrast, we show that the decision problem whether a given split graph can be partitioned into connected parts of order a 1,a 2,...,a k for a given partition a 1,a 2,...,a k of the order of the graph, is NP-hard.
U2 - 10.1007/978-3-642-10217-2_13
DO - 10.1007/978-3-642-10217-2_13
M3 - Conference contribution
SN - 978-3-642-10216-5
T3 - Lecture Notes in Computer Science
SP - 105
EP - 112
BT - Combinatorial Algorithms (20th International Workshop, IWOCA 2009, Hradec nad Moravici, Czech Republic, June 28-July 2, 2009, Revised Selected Papers)
A2 - Fiala, J.
A2 - Kratochvil, J.
A2 - Miller, M.
PB - Springer
CY - Berlin
ER -