The hardness of approximation: gap location
- 31 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
No abstract availableKeywords
This publication has 18 references indexed in Scilit:
- A well-characterized approximation problemPublished 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
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991
- NP completeness of finding the chromatic index of regular graphsJournal of Algorithms, 1983
- The NP-Completeness of Edge-ColoringSIAM Journal on Computing, 1981
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976
- Planar 3-colorability is polynomial completeACM SIGACT News, 1973
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972