RenĂ© van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, and Gerhard J. Woeginger. Star partitions of perfect graphs. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP'14), Copenhagen, Denmark, volume 8572 of Lecture Notes in Computer Science, pages 174–185. Springer, 2014. The final version of this article appeared in Journal of Graph Theory.

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 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-hard cases, for example, on grid graphs and chordal graphs.

bib | DOI | journal version ] Back


This file was generated by bibtex2html 1.98.