An approximation of the minimum vertex cover in a graph

DOI10.1007/BF03167363zbMath1306.05193OpenAlexW2041995230MaRDI QIDQ2258357

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

graphcyclematchingapproximation algorithmvertex 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)

Related Items (3)

Connected Vertex Covers in Dense Graphs ⋮ Approximating the dense set-cover problem ⋮ Connected vertex covers in dense graphs

Cites Work

• Optimization, approximation, and complexity classes
• Approximation algorithms for NP-complete problems on planar graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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