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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

10 Citaten (Scopus)

4 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	567-575
Tijdschrift	European Journal of Combinatorics
Volume	34
Nummer van het tijdschrift	3
DOI's	https://doi.org/10.1016/j.ejc.2011.09.044
Status	Gepubliceerd - 2013

Toegang tot document

10.1016/j.ejc.2011.09.044

Citeer dit

@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

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit