Improved approximations of independent sets in bounded-degree graphs
- 1 January 1994
- book chapter
- Published by Springer Nature
- p. 195-206
- https://doi.org/10.1007/3-540-58218-5_18
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- Improved non-approximability resultsPublished by Association for Computing Machinery (ACM) ,1994
- Greed is goodPublished by Association for Computing Machinery (ACM) ,1994
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992
- 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
- Efficient bounds for the stable set, vertex cover and set packing problemsDiscrete Applied Mathematics, 1983
- A note on the independence number of triangle-free graphsDiscrete Mathematics, 1983
- On Turán’s theorem for sparse graphsCombinatorica, 1981
- A note on Ramsey numbersJournal of Combinatorial Theory, Series A, 1980
- Some remarks on chromatic graphsColloquium Mathematicum, 1967