A graph approximation heuristic for the vertex cover problem on planar graphs
DOI10.1016/0377-2217(94)90425-1zbMATH Open0819.90122OpenAlexW2036887185MaRDI QIDQ1328583FDOQ1328583
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
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
Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Matching, Euler tours and the Chinese postman
- Paths, Trees, and Flowers
- Title not available (Why is that?)
- Some simplified NP-complete graph problems
- A linear-time approximation algorithm for the weighted vertex cover problem
- Vertex packings: Structural properties and algorithms
- Title not available (Why is that?)
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Efficient bounds for the stable set, vertex cover and set packing problems
- On approximation problems related to the independent set and vertex cover problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Eulerian Walks in Graphs
- An Application of Duality to Edge-Deletion Problems
- Minimum-maximal matching in series-parallel graphs
Cited In (8)
- Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
- Title not available (Why is that?)
- Computational complexity of the vertex cover problem in the class of planar triangulations
- An analysis of heuristics for graph planarization
- Heuristics for automated knowledge source integration and service composition
- A decomposition strategy for the vertex cover problem
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- 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)
