Improved non-approximability results for minimum vertex cover with density constraints
Open Access
- 1 August 1999
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 225 (1-2) , 113-128
Abstract
No abstract availableKeywords
This publication has 7 references indexed in Scilit:
- Derandomized graph productscomputational complexity, 1995
- On the hardness of approximating minimization problemsJournal of the ACM, 1994
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Completeness in approximation classesInformation and Computation, 1991
- Ramanujan graphsCombinatorica, 1988
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976