2010 | OriginalPaper | Buchkapitel
An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion
verfasst von : Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The
Pathwidth One Vertex Deletion
(POVD) problem, given an undirected graph
G
and an integer
k
, asks whether one can delete at most
k
vertices from
G
so that the remaining graph has pathwidth at most 1. Recently Philip et al.[14] initiated the study of the parameterized complexity of (POVD) and have shown a quartic kernel and a 7
k
n
O
(1)
algorithm. In this paper we improve these results by showing a quadratic kernel and a 4.65
k
n
O
(1)
algorithm.