Premium
Improvement on vertex cover for low‐degree graphs
Author(s) -
Chen Jianer,
Liu Lihua,
Jia Weijia
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200007)35:4<253::aid-net3>3.0.co;2-k
Subject(s) - vertex cover , combinatorics , bounded function , degree (music) , edge cover , vertex (graph theory) , mathematics , independent set , feedback vertex set , neighbourhood (mathematics) , graph , discrete mathematics , mathematical analysis , physics , acoustics
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.2192 k k ), 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.