Measuring indifference: Unit interval vertex deletion

René Van Bevern, Christian Komusiewicz, Hannes Moser, Rolf Niedermeier

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

22 Цитирования (Scopus)

Аннотация

Making a graph unit interval by a minimum number of vertex deletions is NP-hard. The problem is motivated by applications in seriation and measuring indifference between data items. We present a fixed-parameter algorithm based on the iterative compression technique that finds in O((14k + 14) k + 1kn6) time a set of k vertices whose deletion from an n-vertex graph makes it unit interval. Additionally, we show that making a graph chordal by at most k vertex deletions is NP-complete even on {claw,net,tent}-free graphs.

Язык оригиналаанглийский
Название основной публикацииGraph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers
Страницы232-243
Число страниц12
DOI
СостояниеОпубликовано - 21 дек 2010
Опубликовано для внешнего пользованияДа
Событие36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010 - Zaros, Crete, Греция
Продолжительность: 28 июн 201030 июн 2010

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

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

Конференция

Конференция36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010
СтранаГреция
ГородZaros, Crete
Период28.06.201030.06.2010

Fingerprint Подробные сведения о темах исследования «Measuring indifference: Unit interval vertex deletion». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Van Bevern, R., Komusiewicz, C., Moser, H., & Niedermeier, R. (2010). Measuring indifference: Unit interval vertex deletion. В Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers (стр. 232-243). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 6410 LNCS). https://doi.org/10.1007/978-3-642-16926-7_22