Partitioning Perfect Graphs into StarsReport as inadecuate

Partitioning Perfect Graphs into Stars - Download this document for free, or read online. Document in PDF available to download.

1 SWT - TUB - Department of Software Engineering and Theoretical Computer Science 2 Northwestern Polytechnical University, Xi-An, China 3 Department of mathematics and computing science Eindhoven

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.

Author: René Van Bevern - Robert Bredereck - Laurent Bulteau - Jiehua Chen - Vincent Froese - Rolf Niedermeier - Gerhard J. Woeginger -



Related documents