×

Improvement on vertex cover for low-degree graphs. (English) Zbl 0974.05078

Summary: 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^kk)\), 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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
90B10 Deterministic network models in operations research
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balasubramanian, Info Process Lett 65 pp 163– (1998) · Zbl 1337.05095 · doi:10.1016/S0020-0190(97)00213-5
[2] Buss, SIAM J Comput 22 pp 560– (1993) · Zbl 0773.68031 · doi:10.1137/0222038
[3] and Vertex cover: Further observation and further improvements, Lecture Notes in Computer Science 1665 (WG’99), Springer, Berlin, 1999, pp. 313-324. · Zbl 0952.68111
[4] and ?Parameterized computational feasibility,? Feasible mathematics II, and (Editors), Birkhauser, Boston, 1995, pp. 219-244.
[5] and Parameterized complexity, Springer-Verlag, New York, 1999. · Zbl 0943.03029 · doi:10.1007/978-1-4612-0515-9
[6] and ?Parameterized complexity: A framework for systematically confronting computational intractability,? Contemporary trends in discrete mathematics: From DIMACS and DIMATIA to the future, and (Editors), AMS-DIMACS Proceedings Series 49, AMS, 1999, pp. 49-99. · doi:10.1090/dimacs/049/04
[7] and Computers and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, 1979.
[8] The art of computer programming, Addison-Wesley, Reading, MA, 1968, Vol. 1.
[9] and ?Upper bounds for vertex cover further improved,? Lecture Notes in Computer Science 1563 (STACS’99), Springer, Berlin, 1999, pp. 561-570.
[10] Nemhauser, Math Program 8 pp 232– (1975) · Zbl 0314.90059 · doi:10.1007/BF01580444
[11] Robson, J Alg 7 pp 425– (1986) · Zbl 0637.68080 · doi:10.1016/0196-6774(86)90032-5
[12] Tarjan, SIAM J Comput 6 pp 537– (1977) · Zbl 0357.68035 · doi:10.1137/0206038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.