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

DOI10.1016/0377-2217(94)90425-1zbMath0819.90122OpenAlexW2036887185MaRDI QIDQ1328583

R. Gary Parker, D. L. Meek

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

planar graphsbipartite graphsheuristicvertex cover problem

Mathematics Subject Classification ID

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

Related Items (1)

Heuristics for automated knowledge source integration and service composition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximation problems related to the independent set and vertex cover problems
• Efficient bounds for the stable set, vertex cover and set packing problems
• Minimum-maximal matching in series-parallel graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Approximation algorithms for combinatorial problems
• Some simplified NP-complete graph problems
• An Application of Duality to Edge-Deletion Problems
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Vertex packings: Structural properties and algorithms
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Matching, Euler tours and the Chinese postman
• Paths, Trees, and Flowers
• Eulerian Walks in Graphs

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