Fully decomposable split graphs

Haitze J. Broersma; Dieter Kratsch; Gerhard Woeginger

doi:10.1007/978-3-642-10217-2_13

Fully decomposable split graphs

Haitze J. Broersma, Dieter Kratsch, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

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	https://doi.org/10.1007/978-3-642-10217-2_13
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

Access to Document

10.1007/978-3-642-10217-2_13

http://eprints.eemcs.utwente.nl/secure2/17838/01/fulltext.pdf

Cite this

@inproceedings{8a7cf61cde074c10bd9af05adb499e04,

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, 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.",

keywords = "METIS-266492, EWI-17838, Graph decomposition - integer partition - computational complexity, IR-71247",

author = "Broersma, {Haitze J.} and Dieter Kratsch and Gerhard Woeginger",

year = "2009",

doi = "10.1007/978-3-642-10217-2_13",

language = "Undefined",

isbn = "978-3-642-10216-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "105--112",

editor = "Jiri Fiala and Jan Kratochvil and Mirka Miller",

booktitle = "Combinatorial Algorithms - Proceedings of the 20th International Workshop IWOCA 2009",

note = "null ; Conference date: 28-06-2009 Through 02-07-2009",

}

Broersma, HJ, Kratsch, D & Woeginger, G 2009, Fully decomposable split graphs. in J Fiala, J Kratochvil & M Miller (eds), Combinatorial Algorithms - Proceedings of the 20th International Workshop IWOCA 2009., 10.1007/978-3-642-10217-2_13, Lecture Notes in Computer Science, vol. 5874, Springer, Berlin, pp. 105-112, 20th International Workshop on Combinatioral Algorithms, IWOCA 2009, Hradec nad Moravicí, Czech Republic, 28/06/09. https://doi.org/10.1007/978-3-642-10217-2_13

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

N1 - Conference code: 20

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

Y2 - 28 June 2009 through 2 July 2009

ER -