On approximation problems related to the independent set and vertex cover problems
- 30 September 1984
- journal article
- Published by Elsevier BV in Discrete Applied Mathematics
- Vol. 9 (1), 1-10
- https://doi.org/10.1016/0166-218x(84)90086-6
Abstract
Some open questions concerning the complexity of approximation algorithms for the Maximum Independent Set and Minimum Vertex Cover Problems are studied. It is shown that those questions are at least as hard as a sample of other open questions concerning approximating NP-hard problems, including Graph Coloring, Set Covering and Dominating Set Problems.Keywords
This publication has 8 references indexed in Scilit:
- Approximation Algorithms for the Set Covering and Vertex Cover ProblemsSIAM Journal on Computing, 1982
- Depth-first search and the vertex cover problemInformation Processing Letters, 1982
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981
- Non deterministic polynomial optimization problems and their approximationsTheoretical Computer Science, 1981
- Applications of a Planar Separator TheoremSIAM Journal on Computing, 1980
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976
- Vertex packings: Structural properties and algorithmsMathematical Programming, 1975