Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Deterministic Parameterized Connected Vertex Cover
verfasst von : Marek Cygan
Erschienen in: Algorithm Theory – SWAT 2012
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
In the
Connected Vertex Cover
problem we are given an undirected graph
G
together with an integer
k
and we are to find a subset of vertices
X
of size at most
k
, such that
X
contains at least one end-point of each edge and such that
X
induces a connected subgraph. For this problem we present a deterministic algorithm running in
O
(2
k
poly(
n
)) time and polynomial space, improving over the previous-best
O
(2.4882
k
poly(
n
)) time deterministic algorithm and
O
(2
k
poly(
n
)) time randomized algorithm. Furthermore, when usage of exponential space is allowed, we present an
O
(2
k
k
(
n
+
m
)) time algorithm that solves a more general variant with real weights.
Finally, we show that in
O
(2
k
poly(
n
)) time and space one can count the number of connected vertex covers of size at most
k
, and this time upper bound can not be improved to
O
((2 −
ε
)
k
poly(
n
)) for any
ε
> 0 under the Strong Exponential Time Hypothesis, as shown by Cygan et al. [CCC’12].