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

2 Citations (Scopus)

1 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, 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/Territory	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

Broersma, H. J., 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 (pp. 105-112). Article 10.1007/978-3-642-10217-2_13 (Lecture Notes in Computer Science; Vol. 5874). Springer. https://doi.org/10.1007/978-3-642-10217-2_13

@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 \$\textbackslash{}alpha\_1,\textbackslash{}alpha\_2,\textbackslash{}dots, \textbackslash{}alpha\_k\$ for every \$\textbackslash{}alpha\_1,\textbackslash{}alpha\_2,\textbackslash{}ldots,\textbackslash{}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 \$\textbackslash{}alpha\_1,\textbackslash{}alpha\_2,\textbackslash{}ldots,\textbackslash{}alpha\_k\$ for a given partition \$\textbackslash{}alpha\_1,\textbackslash{}alpha\_2,\textbackslash{}ldots,\textbackslash{}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",

address = "Germany",

note = "20th International Workshop on Combinatioral Algorithms, IWOCA 2009 ; 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

T2 - 20th International Workshop on Combinatioral Algorithms, IWOCA 2009

Y2 - 28 June 2009 through 2 July 2009

ER -