An approximation of the minimum vertex cover in a graph
- 1 October 1999
- journal article
- Published by Springer Nature in Japan Journal of Industrial and Applied Mathematics
- Vol. 16 (3) , 369-375
- https://doi.org/10.1007/bf03167363
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- Approximating dense cases of covering problemsPublished by American Mathematical Society (AMS) ,1998
- Some optimal inapproximability resultsPublished by Association for Computing Machinery (ACM) ,1997
- Improved non-approximability results for vertex cover with density constraintsPublished by Springer Nature ,1996
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- Improved approximations of independent sets in bounded-degree graphsPublished by Springer Nature ,1994
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Some further approximation algorithms for the vertex cover problemPublished by Springer Nature ,1983
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972