Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141411 | Discrete Optimization | 2016 | 11 Pages |
Abstract
Let Pâ denote a path in a graph G=(V,E) with â vertices. A vertex cover Pâ set C in G is a vertex subset such that every Pâ in G has at least a vertex in C. The Vertex CoverPâ problem is to find a vertex cover Pâ set of minimum cardinality in a given graph. This problem is NP-hard for any integer â⩾2. The parameterized version of Vertex CoverPâ problem called k-Vertex CoverPâ asks whether there exists a vertex cover Pâ set of size at most k in the input graph. In this paper, we give two fixed parameter algorithms to solve the k-Vertex CoverP3 problem. The first algorithm runs in time Oâ(1.7964k) in polynomial space and the second algorithm runs in time Oâ(1.7485k) in exponential space. Both algorithms are faster than previous known fixed-parameter algorithms.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung, Peter Rossmanith, Ping-Chen Su,