Abstract
| Original language | English |
|---|---|
| Pages (from-to) | 567-575 |
| Number of pages | 9 |
| Journal | European journal of combinatorics |
| Volume | 34 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 2013 |
Fingerprint
Keywords
- EWI-22740
- MSC-05C
- Fully decomposable
- Arbitrarily vertex decomposable
- Partitioning
- METIS-296435
- IR-83468
- Split graph
Cite this
}
Fully decomposable split graphs. / Broersma, Haitze J.; Kratsch, Dieter; Woeginger, Gerhard.
In: European journal of combinatorics, Vol. 34, No. 3, 2013, p. 567-575.Research output: Contribution to journal › Article › Academic › peer-review
TY - JOUR
T1 - Fully decomposable split graphs
AU - Broersma, Haitze J.
AU - Kratsch, Dieter
AU - Woeginger, Gerhard
PY - 2013
Y1 - 2013
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, that is, whether it can be partitioned into connected parts of orders α1,α2,...,αk for every α1,α2,...,α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 orders α1,α2,...,αk for a given partition α1,α2,...,α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, that is, whether it can be partitioned into connected parts of orders α1,α2,...,αk for every α1,α2,...,α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 orders α1,α2,...,αk for a given partition α1,α2,...,αk of the order of the graph, is NP-hard.
KW - EWI-22740
KW - MSC-05C
KW - Fully decomposable
KW - Arbitrarily vertex decomposable
KW - Partitioning
KW - METIS-296435
KW - IR-83468
KW - Split graph
U2 - 10.1016/j.ejc.2011.09.044
DO - 10.1016/j.ejc.2011.09.044
M3 - Article
VL - 34
SP - 567
EP - 575
JO - European journal of combinatorics
JF - European journal of combinatorics
SN - 0195-6698
IS - 3
ER -