Broersma, H. J. and Kratsch, D. and Woeginger, G. J. (2009) 'Fully decomposable split graphs.', in Combinatorial algorithms : 20th International Workshop, IWOCA 2009, 28 June - 2 July 2009, Hradec nad Moravicí, Czech Republic ; revised selected papers. Heidelberg: Springer, pp. 105-112. Lecture notes in computer science. (5874).
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 α₁,α₂,...,αk for every α₁,α₂,...,α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 α₁,α₂,...,αk for a given partition α₁,α₂,...,αk of the order of the graph, is NP-hard.
|Item Type:||Book chapter|
|Keywords:||Graph decomposition, Integer partition, Computational complexity.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-10217-2_13|
|Record Created:||01 Mar 2010 12:50|
|Last Modified:||08 Dec 2010 12:00|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|