Partitioning perfect graphs into stars

R. van Bevern, R. Bredereck, L. Bulteau, J. Chen, V. Froese, R. Niedermeier, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

3 Citaten (Scopus)


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.

Originele taal-2Engels
Pagina's (van-tot)297-335
Aantal pagina's39
TijdschriftJournal of Graph Theory
Nummer van het tijdschrift2
StatusGepubliceerd - 1 jun 2017

Vingerafdruk Duik in de onderzoeksthema's van 'Partitioning perfect graphs into stars'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    van Bevern, R., Bredereck, R., Bulteau, L., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2017). Partitioning perfect graphs into stars. Journal of Graph Theory, 85(2), 297-335.