A graph approximation heuristic for the vertex cover problem on planar graphs

DOI10.1016/0377-2217(94)90425-1MaRDI QIDQ1328583zbMATH OpenOpenAlexFDO

Authors D. L. Meek, R. G. Parker

Publication date 26 July 1994

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(94)90425-1

zbMATH Keywords

heuristicvertex cover problemplanar graphsbipartite graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 19175
• New approximation algorithms for the vertex cover problem
• An edge-reduction algorithm for the vertex cover problem
• An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
• Divide-and-conquer approximation algorithm for vertex cover

Cites work

• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3750313 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 193499 (Why is no real title available?)
• scientific article; zbMATH DE number 3575605 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear-time approximation algorithm for the weighted vertex cover problem
• An Application of Duality to Edge-Deletion Problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for combinatorial problems
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Efficient bounds for the stable set, vertex cover and set packing problems
• Eulerian Walks in Graphs
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Matching, Euler tours and the Chinese postman
• Minimum-maximal matching in series-parallel graphs
• On approximation problems related to the independent set and vertex cover problems
• Paths, Trees, and Flowers
• Some simplified NP-complete graph problems
• Vertex packings: Structural properties and algorithms

Cited in

(8)

• A decomposition strategy for the vertex cover problem
• Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
• Heuristics for automated knowledge source integration and service composition
• Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
• An analysis of heuristics for graph planarization
• Computational complexity of the vertex cover problem in the class of planar triangulations
• scientific article; zbMATH DE number 1953099 (Why is no real title available?)
• Approximating the minimum hub cover problem on planar graphs

This page was built for publication: A graph approximation heuristic for the vertex cover problem on planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1328583)