Star partitions of perfect graphs

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

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

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

Язык оригиналаанглийский
Название основной публикацииAutomata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
ИздательSpringer-Verlag GmbH and Co. KG
Страницы174-185
Число страниц12
ИзданиеPART 1
ISBN (печатное издание)9783662439470
DOI
СостояниеОпубликовано - 1 янв 2014
Опубликовано для внешнего пользованияДа
Событие41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Дания
Продолжительность: 8 июл 201411 июл 2014

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
НомерPART 1
Том8572 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
СтранаДания
ГородCopenhagen
Период08.07.201411.07.2014

Fingerprint Подробные сведения о темах исследования «Star partitions of perfect graphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Van Bevern, R., Bredereck, R., Bulteau, L., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2014). Star partitions of perfect graphs. В Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings (PART 1 ред., стр. 174-185). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 8572 LNCS, № PART 1). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-662-43948-7_15