Fully decomposable split graphs

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

doi:10.1016/j.ejc.2011.09.044

Fully decomposable split graphs

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

Research output: Contribution to journal › Article › Academic › peer-review

10 Citations (Scopus)

4 Downloads (Pure)

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, that is, whether it can be partitioned into connected parts of orders a1,a2,…,ak for every a1,a2,…,ak 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 a1,a2,…,ak for a given partition a1,a2,…,ak of the order of the graph, is NP-hard.

Original language	English
Pages (from-to)	567-575
Journal	European Journal of Combinatorics
Volume	34
Issue number	3
DOIs	https://doi.org/10.1016/j.ejc.2011.09.044
Publication status	Published - 2013

Access to Document

10.1016/j.ejc.2011.09.044

Cite this

@article{de83fe121d124e1d823a3b9a810451cf,

title = "Fully decomposable split graphs",

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, that is, whether it can be partitioned into connected parts of orders a1,a2,…,ak for every a1,a2,…,ak 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 a1,a2,…,ak for a given partition a1,a2,…,ak of the order of the graph, is NP-hard.",

author = "H.J. Broersma and D. Kratsch and G.J. Woeginger",

year = "2013",

doi = "10.1016/j.ejc.2011.09.044",

language = "English",

volume = "34",

pages = "567--575",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Fully decomposable split graphs

AU - Broersma, H.J.

AU - Kratsch, D.

AU - Woeginger, G.J.

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 a1,a2,…,ak for every a1,a2,…,ak 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 a1,a2,…,ak for a given partition a1,a2,…,ak 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 a1,a2,…,ak for every a1,a2,…,ak 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 a1,a2,…,ak for a given partition a1,a2,…,ak of the order of the graph, is NP-hard.

U2 - 10.1016/j.ejc.2011.09.044

DO - 10.1016/j.ejc.2011.09.044

M3 - Article

SN - 0195-6698

VL - 34

SP - 567

EP - 575

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 3

ER -

Fully decomposable split graphs

Abstract

Access to Document

Fingerprint

Cite this