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
Event20th International Workshop on Combinatioral Algorithms, IWOCA 2009 - Hradec nad Moravicí, Czech Republic, Hradec nad Moravicí, Czech Republic
Duration: 28 Jun 20092 Jul 2009
Conference number: 20

Publication series

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

Conference

Conference20th International Workshop on Combinatioral Algorithms, IWOCA 2009
Abbreviated titleIWOCA 2009
CountryCzech Republic
CityHradec nad Moravicí
Period28/06/092/07/09
Other28 June - 2 July 2009

Keywords

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

Cite this