Partitioning Perfect Graphs into Stars

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

Результат исследования: Научные публикации в периодических изданияхстатья

3 Цитирования (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.

Язык оригиналаанглийский
Страницы (с-по)297-335
Число страниц39
ЖурналJournal of Graph Theory
Том85
Номер выпуска2
DOI
СостояниеОпубликовано - 1 июн 2017

Fingerprint Подробные сведения о темах исследования «Partitioning Perfect Graphs into Stars». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать