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 -