On approximation properties of the Independent set problem for degree 3 graphs
- 1 January 1995
- book chapter
- Published by Springer Nature
- p. 449-460
- https://doi.org/10.1007/3-540-60220-8_84
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- Greed is goodPublished by Association for Computing Machinery (ACM) ,1994
- Proof verification and hardness of approximation problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991
- Efficient bounds for the stable set, vertex cover and set packing problemsDiscrete Applied Mathematics, 1983
- Vertex packings: Structural properties and algorithmsMathematical Programming, 1975
- Three short proofs in graph theoryJournal of Combinatorial Theory, Series B, 1975
- On colouring the nodes of a networkMathematical Proceedings of the Cambridge Philosophical Society, 1941