Improvement on Vertex Cover for low-degree graphs

Authors
Chen, JN Liu, LH Jia, WJ
Citation
Jn. Chen et al., Improvement on Vertex Cover for low-degree graphs, NETWORKS, 35(4), 2000, pp. 253-259
Citations number
12
Categorie Soggetti
Computer Science & Engineering
Journal title
NETWORKS
ISSN journal
00283045 → ACNP
Volume
35
Issue
4
Year of publication
2000
Pages
253 - 259
Database
ISI
SICI code
0028-3045(200007)35:4<253:IOVCFL>2.0.ZU;2-D
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.2192(k)k), where k is the number of vertices in a minimum vertex c over of the graph. Our algorithm also improves previous algorithms on the I ndependent Set problem on graphs with degree bounded by 3. (C) 2000 John Wi ley & Sons, Inc.