An approximation of the minimum vertex cover in a graph

DOI10.1007/BF03167363MaRDI QIDQ2258357zbMATH OpenOpenAlexFDO

Authors Hiroshi Nagamochi, Toshihide Ibaraki

Publication date 3 March 2015

Published in Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf03167363

zbMATH Keywords

approximation algorithmcyclegraphmatchingvertex cover

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Divide-and-conquer approximation algorithm for vertex cover
• An edge-reduction algorithm for the vertex cover problem
• scientific article; zbMATH DE number 3869066
• scientific article; zbMATH DE number 5631194
• scientific article; zbMATH DE number 19175

Cites work

• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• scientific article; zbMATH DE number 1003268 (Why is no real title available?)
• scientific article; zbMATH DE number 3853131 (Why is no real title available?)
• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1163714 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 753971 (Why is no real title available?)
• Optimization, approximation, and complexity classes

Cited in

(17)

• Minimal cut cover of a graph with an application to the testing of electronic boards
• Approximating the minimum tour cover of a digraph
• Approximating the dense set-cover problem
• Minimum vertex cover in ball graphs through local search
• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• Minimum vertex covering problem based on the shortest path algorithm
• Connected Vertex Covers in Dense Graphs
• Divide-and-conquer approximation algorithm for vertex cover
• scientific article; zbMATH DE number 5631194 (Why is no real title available?)
• scientific article; zbMATH DE number 19175 (Why is no real title available?)
• scientific article; zbMATH DE number 3894490 (Why is no real title available?)
• Approximation of Self-stabilizing Vertex Cover Less Than 2
• An approximation algorithm for the minimum co-path set problem
• On approximating minimum vertex cover for graphs with perfect matching
• Algorithms - ESA 2003
• Approximating the minimum hub cover problem on planar graphs
• Connected vertex covers in dense graphs

This page was built for publication: An approximation of the minimum vertex cover in a graph

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