Аннотация
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 |