Fully decomposable split graphs

Haitze J. Broersma, Dieter Kratsch, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
8 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, that is, whether it can be partitioned into connected parts of orders α1,α2,...,αk for every α1,α2,...,α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 orders α1,α2,...,αk for a given partition α1,α2,...,αk of the order of the graph, is NP-hard.
Original languageEnglish
Pages (from-to)567-575
Number of pages9
JournalEuropean journal of combinatorics
Volume34
Issue number3
DOIs
Publication statusPublished - 2013

Fingerprint

Split Graph
Decomposable
Graph in graph theory
Decision problem
Polynomial-time Algorithm
Partitioning
NP-complete problem
Partition

Keywords

  • EWI-22740
  • MSC-05C
  • Fully decomposable
  • Arbitrarily vertex decomposable
  • Partitioning
  • METIS-296435
  • IR-83468
  • Split graph

Cite this

Broersma, Haitze J. ; Kratsch, Dieter ; Woeginger, Gerhard. / Fully decomposable split graphs. In: European journal of combinatorics. 2013 ; Vol. 34, No. 3. pp. 567-575.
@article{b907bc22806b45858ef44ce8cea90b25,
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 α1,α2,...,αk for every α1,α2,...,α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 orders α1,α2,...,αk for a given partition α1,α2,...,αk of the order of the graph, is NP-hard.",
keywords = "EWI-22740, MSC-05C, Fully decomposable, Arbitrarily vertex decomposable, Partitioning, METIS-296435, IR-83468, Split graph",
author = "Broersma, {Haitze J.} and Dieter Kratsch and Gerhard 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",

}

Fully decomposable split graphs. / Broersma, Haitze J.; Kratsch, Dieter; Woeginger, Gerhard.

In: European journal of combinatorics, Vol. 34, No. 3, 2013, p. 567-575.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Fully decomposable split graphs

AU - Broersma, Haitze J.

AU - Kratsch, Dieter

AU - Woeginger, Gerhard

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 α1,α2,...,αk for every α1,α2,...,α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 orders α1,α2,...,αk for a given partition α1,α2,...,α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, that is, whether it can be partitioned into connected parts of orders α1,α2,...,αk for every α1,α2,...,α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 orders α1,α2,...,αk for a given partition α1,α2,...,αk of the order of the graph, is NP-hard.

KW - EWI-22740

KW - MSC-05C

KW - Fully decomposable

KW - Arbitrarily vertex decomposable

KW - Partitioning

KW - METIS-296435

KW - IR-83468

KW - Split graph

U2 - 10.1016/j.ejc.2011.09.044

DO - 10.1016/j.ejc.2011.09.044

M3 - Article

VL - 34

SP - 567

EP - 575

JO - European journal of combinatorics

JF - European journal of combinatorics

SN - 0195-6698

IS - 3

ER -