Abstract
| 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 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer Verlag |
| Volume | 5874 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Keywords
- METIS-266492
- EWI-17838
- Graph decomposition - integer partition - computational complexity
- IR-71247
Cite this
}
Fully decomposable split graphs. / Broersma, Haitze J.; Kratsch, Dieter; Woeginger, Gerhard.
Combinatorial Algorithms - Proceedings of the 20th International Workshop IWOCA 2009. ed. / Jiri Fiala; Jan Kratochvil; Mirka Miller. Berlin : Springer, 2009. p. 105-112 10.1007/978-3-642-10217-2_13 (Lecture Notes in Computer Science; Vol. 5874).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - Fully decomposable split graphs
AU - Broersma, Haitze J.
AU - Kratsch, Dieter
AU - Woeginger, Gerhard
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 $\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.
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 $\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.
KW - METIS-266492
KW - EWI-17838
KW - Graph decomposition - integer partition - computational complexity
KW - IR-71247
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 - Proceedings of the 20th International Workshop IWOCA 2009
A2 - Fiala, Jiri
A2 - Kratochvil, Jan
A2 - Miller, Mirka
PB - Springer
CY - Berlin
ER -