Linear-time computation of a linear problem kernel for dominating set on planar graphs

René Van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier, Mathias Weller

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

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

Аннотация

We present a linear-time kernelization algorithm that transforms a given planar graph G with domination number γ(G) into a planar graph G' of size O(γ(G)) with γ(G) = γ(G'). In addition, a minimum dominating set for G can be inferred from a minimum dominating set for G'. In terms of parameterized algorithmics, this implies a linear-size problem kernel for the NP-hard Dominating Set problem on planar graphs, where the kernelization takes linear time. This improves on previous kernelization algorithms that provide linear-size kernels in cubic time.

Язык оригиналаанглийский
Название основной публикацииParameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers
Страницы194-206
Число страниц13
DOI
СостояниеОпубликовано - 22 мар 2012
Опубликовано для внешнего пользованияДа
Событие6th International Symposium on Parameterized and Exact Computation, IPEC 2011 - Saarbrucken, Германия
Продолжительность: 6 сен 20118 сен 2011

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

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

Конференция

Конференция6th International Symposium on Parameterized and Exact Computation, IPEC 2011
СтранаГермания
ГородSaarbrucken
Период06.09.201108.09.2011

Fingerprint Подробные сведения о темах исследования «Linear-time computation of a linear problem kernel for dominating set on planar graphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать