Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time

This publication has 18 references indexed in Scilit:

• Finding and certifying a large hidden clique in a semirandom graph
  Random Structures & Algorithms, 2000
• Finding a large hidden clique in a random graph
  Random Structures & Algorithms, 1998
• Spectral techniques in graph algorithms
  Published by Springer Nature ,1998
• Coloring random graphs in polynomial expected time
  Published by Springer Nature ,1993
• A still better performance guarantee for approximate graph coloring
  Information Processing Letters, 1993
• The solution of some random NP-hard problems in polynomial expected time
  Journal of Algorithms, 1989
• The chromatic number of random graphs
  Combinatorica, 1988
• Eigenvalues and graph bisection: An average-case analysis
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1987
• The eigenvalues of random symmetric matrices
  Combinatorica, 1981
• Reducibility among Combinatorial Problems
  Published by Springer Nature ,1972