Improvement on vertex cover for low-degree graphs
Jianer Chen, Lihua Liu, Weijia Jia · Networks · 2000
We present an improved algorithm for the Vertex Cover problem on graphs of degree bounded by 3 (3DVC). We show that the 3DVC problem can be solved in time O(1.2192kk), where k is the number of vertices in a minimum vertex cover of the graph. Our algorithm also improves previous algorithms on the Independent Set problem on graphs with degree bounded by 3. © 2000 John Wiley & Sons, Inc.