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 $\alpha_1,\alpha_2,\dots, \alpha_k$ for every $\alpha_1,\alpha_2,\ldots,\alpha_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 $\alpha_1,\alpha_2,\ldots,\alpha_k$ for a given partition $\alpha_1,\alpha_2,\ldots,\alpha_k$ of the order of the graph, is NP-hard.
Original language | Undefined |
---|---|
Title of host publication | Combinatorial Algorithms - Proceedings of the 20th International Workshop IWOCA 2009 |
Editors | Jiri Fiala, Jan Kratochvil, Mirka Miller |
Place of Publication | Berlin |
Publisher | Springer |
Pages | 105-112 |
Number of pages | 8 |
ISBN (Print) | 978-3-642-10216-5 |
DOIs | |
Publication status | Published - 2009 |
Event | 20th International Workshop on Combinatioral Algorithms, IWOCA 2009 - Hradec nad Moravicí, Czech Republic, Hradec nad Moravicí, Czech Republic Duration: 28 Jun 2009 → 2 Jul 2009 Conference number: 20 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Verlag |
Volume | 5874 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 20th International Workshop on Combinatioral Algorithms, IWOCA 2009 |
---|---|
Abbreviated title | IWOCA 2009 |
Country | Czech Republic |
City | Hradec nad Moravicí |
Period | 28/06/09 → 2/07/09 |
Other | 28 June - 2 July 2009 |
Keywords
- METIS-266492
- EWI-17838
- Graph decomposition - integer partition - computational complexity
- IR-71247