On approximation problems related to the independent set and vertex cover problems
- 30 September 1984
- journal article
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 9 (1) , 1-10
- https://doi.org/10.1016/0166-218x(84)90086-6
Abstract
No abstract availableKeywords
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