Computer Science – Data Structures and Algorithms
Scientific paper
2012-02-29
Computer Science
Data Structures and Algorithms
Scientific paper
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 moreover X induces a connected subgraph. For this problem we present a deterministic algorithm running in O(2^k n^O(1)) time and polynomial space, improving over previously best O(2.4882^k n^O(1)) deterministic algorithm and O(2^k n^O(1)) 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 arbitrary real weights. Finally, we show that in O(2k k(n + m)) time and O(2^k k) space one can count the number of connected vertex covers of size at most k, which can not be improved to O((2 - eps)^k nO(1)) for any eps > 0 under the Strong Exponential Time Hypothesis, as shown by Cygan et al. [CCC'12].
No associations
LandOfFree
Deterministic parameterized connected vertex cover does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Deterministic parameterized connected vertex cover, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic parameterized connected vertex cover will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-526322