Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time
Authors:
- 1 June 2002
- journal article
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 6 (2) , 143-155
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- Finding and certifying a large hidden clique in a semirandom graphRandom Structures & Algorithms, 2000
- Coloring random graphs in polynomial expected timeLecture Notes in Computer Science, 1993
- A still better performance guarantee for approximate graph coloringInformation Processing Letters, 1993
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992
- A new isoperimetric inequality for product measure and the tails of sums of independent random variablesGeometric and Functional Analysis, 1991
- The chromatic number of random graphsCombinatorica, 1991
- The solution of some random NP-hard problems in polynomial expected timeJournal of Algorithms, 1989
- The chromatic number of random graphsCombinatorica, 1988
- The eigenvalues of random symmetric matricesCombinatorica, 1981
- Reducibility among Combinatorial Problems1972