Some APX-completeness results for cubic graphs
Authors:
- 1 April 2000
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 237 (1-2) , 123-134
Abstract
No abstract availableKeywords
This publication has 16 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
- Greedy approximations of independent sets in low degree graphs1995
- Structure in approximation classes1995
- 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
- Completeness in approximation classesInformation and Computation, 1991
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991