Improvement on vertex cover for lowdegree graphs
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
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.