Improved non-approximability results for vertex cover with density constraints
- 1 January 1996
- book chapter
- Published by Springer Nature
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- On syntactic versus computational views of approximabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximating clique is almost NP-completePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- Testing of the long code and hardness for cliquePublished by Association for Computing Machinery (ACM) ,1996
- On approximation properties of the Independent set problem for degree 3 graphsPublished by Springer Nature ,1995
- Probabilistic checking of proofs; a new characterization of NPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Completeness in approximation classesInformation and Computation, 1991
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989
- Ramanujan graphsCombinatorica, 1988
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972