Kernelization through tidying: A case study based on s-plex cluster vertex deletion

René Van Bevern, Hannes Moser, Rolf Niedermeier

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

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

Аннотация

We introduce the NP-hard graph-based data clustering problem s -Plex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s∈-∈1 other vertices; cliques are 1-plexes. We propose a new method for kernelizing a large class of vertex deletion problems and illustrate it by developing an O(k 2 s3)-vertex problem kernel for s -Plex Cluster Vertex Deletion that can be computed in O(ksn2) time, where n is the number of graph vertices. The corresponding "kernelization through tidying" exploits polynomial-time approximation results.

Язык оригиналаанглийский
Название основной публикацииLATIN 2010
Подзаголовок основной публикацииTheoretical Informatics - 9th Latin American Symposium, Proceedings
Страницы527-538
Число страниц12
DOI
СостояниеОпубликовано - 18 июн 2010
Опубликовано для внешнего пользованияДа
Событие9th Latin American Theoretical Informatics Symposium, LATIN 2010 - Oaxaca, Мексика
Продолжительность: 19 апр 201023 апр 2010

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

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

Конференция

Конференция9th Latin American Theoretical Informatics Symposium, LATIN 2010
СтранаМексика
ГородOaxaca
Период19.04.201023.04.2010

Fingerprint Подробные сведения о темах исследования «Kernelization through tidying: A case study based on s-plex cluster vertex deletion». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать