Skip to main content

Research Repository

Advanced Search

Fully decomposable split graphs

Broersma, H.J.; Kratsch, D.; Woeginger, G.J.

Authors

H.J. Broersma

D. Kratsch

G.J. Woeginger



Abstract

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.

Citation

Broersma, H., Kratsch, D., & Woeginger, G. (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 (105-112). https://doi.org/10.1007/978-3-642-10217-2_13

Conference Name 20th International Workshop on Combinatorial Algorithms (IWOCA 2009)
Conference Location Hradec nad Moravicí, Czech Republic
Start Date Jun 28, 2023
End Date Jul 2, 2009
Publication Date Nov 1, 2009
Deposit Date Mar 1, 2010
Pages 105-112
Series Title Lecture notes in computer science
Series Number 5874
Series ISSN 0302-9743
Book Title Combinatorial algorithms : 20th International Workshop, IWOCA 2009, 28 June - 2 July 2009, Hradec nad Moravicí, Czech Republic ; revised selected papers.
DOI https://doi.org/10.1007/978-3-642-10217-2_13
Keywords Graph decomposition, Integer partition, Computational complexity.