Some APX-completeness results for cubic graphs
Top Cited Papers
- 28 April 2000
- journal article
- Published by Elsevier BV in Theoretical Computer Science
- Vol. 237 (1-2), 123-134
- https://doi.org/10.1016/s0304-3975(98)00158-3
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 graphsPublished by Springer Science and Business Media LLC ,1995
- Structure in approximation classesPublished by Springer Science and Business Media LLC ,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
- Completeness in approximation classesInformation and Computation, 1991
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991