The problem instance of Vertex Cover consists of an undirected graph G = (V, E) and a positive integer k, the question is whether there exists a subset C ⊂-V of vertices such that each edge in E has at least one of its endpoints in C with |C|≤ k. We improve two recent worst case upper bounds for Vertex Cover. First, Balasubramanian et al. showed that Vertex Cover can be solved in time O(kn + 1.32472kk2), where n is the number of vertices in G. Afterwards, Downey et al. improved this to O(kn + 1.31951kk2). Bringing the exponential base significantly below 1.3, we present the new upper bound O(kn + 1.29175kk2).
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- Upper Bounds for Vertex Cover Further Improved
- Springer Berlin Heidelberg