Partitioning Perfect Graphs into Stars

René van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same-size stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-complete cases, for example, on grid graphs and chordal graphs.

Original languageEnglish
Pages (from-to)297-335
Number of pages39
JournalJournal of Graph Theory
Volume85
Issue number2
DOIs
Publication statusPublished - 1 Jun 2017

Keywords

  • generalized matching problem
  • graph algorithms
  • graph factors
  • graph packing
  • P-Partition
  • INTERVAL-GRAPHS
  • PATH PARTITION
  • P-3-PARTITION
  • ORIENTATIONS
  • RECOGNITION ALGORITHM
  • COMPLEXITY
  • CHORDAL GRAPHS
  • BIPARTITE GRAPHS

Fingerprint

Dive into the research topics of 'Partitioning Perfect Graphs into Stars'. Together they form a unique fingerprint.

Cite this