Improvement on vertex cover for lowdegree graphs Academic Article uri icon

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.

published proceedings

  • Networks

author list (cited authors)

  • Chen, J., Liu, L., & Jia, W.

citation count

  • 28

complete list of authors

  • Chen, Jianer||Liu, Lihua||Jia, Weijia

publication date

  • July 2000

publisher