Hardness of approximating problems on cubic graphs
- 1 January 1997
- book chapter
- Published by Springer Nature
- p. 288-298
- https://doi.org/10.1007/3-540-62592-5_80
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- Cubic graphsACM Computing Surveys, 1995
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- The complexity and approximability of finding maximum feasible subsystems of linear relationsTheoretical Computer Science, 1995
- On approximation properties of the Independent set problem for degree 3 graphsPublished by Springer Nature ,1995
- Structure in approximation classesPublished by Springer Nature ,1995
- On the hardness of approximating minimization problemsJournal of the ACM, 1994
- Approximating the minimum maximal independence numberInformation Processing Letters, 1993
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991
- Recursive construction for 3-regular expandersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987