On approximating a vertex cover for planar graphs

ABSTRACT

The approximation problem for vertex cover of n-vertex planar graphs is treated. Two results are presented: (1) A linear time approximation algorithm for which the (error) performance bound is 2/3. (2) An O(n log n) time approximation scheme.

REFERENCES

• 1: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 2: Hochbaum, D.S., "Approximation Algorithm for the Weighted Set Covering and Node Cover Problems", W.P. #64-79-80, GSIA, Carnegie-Mellon University, April 1980.
• 3: Bar-Yehuda, R., and Even, S., "A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problems", J. of Algorithms, Vol. 2, 1981, pp. 198-203.
• 4: Hochbaum, D.S., "Efficient Bounds for the Stable Set, Vertex Cover and Set Packing Problems", W.P. #50-80-81, GSIA, Carnegie-Mellon University, May 1981.
• 5: Lipton, R.J., and Tarjan, R.E., "Applications of a Planar Separator Theorem", SIAM J. Comput., Vol. 9, No.3, August 1980, pp. 615-627.
• 6: Itai, A., and Rodeh, M., "Finding a Minimum Circuit in a Graph", SIAM J. Comput., Vol. 7, No. 4, November 1978, pp. 413-423.
• 7: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 8: Tarjan, R.E., "Depth-First Search and Linear Graph Algorithms," SIAM J. Comput., Vol. 1, 1972, pp. 146-160.