Fully decomposable split graphs

Haitze J. Broersma, Dieter Kratsch, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageUndefined
Title of host publicationCombinatorial Algorithms - Proceedings of the 20th International Workshop IWOCA 2009
EditorsJiri Fiala, Jan Kratochvil, Mirka Miller
Place of PublicationBerlin
PublisherSpringer
Pages105-112
Number of pages8
ISBN (Print)978-3-642-10216-5
DOIs
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume5874
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • METIS-266492
  • EWI-17838
  • Graph decomposition - integer partition - computational complexity
  • IR-71247

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). [10.1007/978-3-642-10217-2_13] (Lecture Notes in Computer Science; Vol. 5874). Berlin: Springer. https://doi.org/10.1007/978-3-642-10217-2_13
Broersma, Haitze J. ; Kratsch, Dieter ; Woeginger, Gerhard. / Fully decomposable split graphs. Combinatorial Algorithms - Proceedings of the 20th International Workshop IWOCA 2009. editor / Jiri Fiala ; Jan Kratochvil ; Mirka Miller. Berlin : Springer, 2009. pp. 105-112 (Lecture Notes in Computer Science).
@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",

}

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. 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 proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Fully decomposable split graphs

AU - Broersma, Haitze J.

AU - Kratsch, Dieter

AU - Woeginger, Gerhard

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

ER -

Broersma HJ, Kratsch D, Woeginger G. Fully decomposable split graphs. In Fiala J, Kratochvil J, Miller M, editors, Combinatorial Algorithms - Proceedings of the 20th International Workshop IWOCA 2009. Berlin: Springer. 2009. p. 105-112. 10.1007/978-3-642-10217-2_13. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-10217-2_13