SIAM Journal on Computing · 1997 · 188 citations · 15 references
ComputingComputer ScienceAlgorithmsCombinatoricsTheory Of ComputationGraph AlgorithmsGraph ColoringGraph TheoryProbabilistic CombinatoricsRandomized ComplexityRandomized ComputationApproximation Algorithms For ColoringColoring Random GraphsPolynomial Time ComplexityPolynomial-time AlgorithmsRandom Graph TheoryRandom GraphsTheoretical ProbabilityVertex Coloring
Abstract. Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G3n,p,3 with high probability, whenever p ≥ c/n, where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p ≥ polylog(n)/n [J. Algorithms, 19 (1995), pp. 204–234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c.
15
The Algebraic Eigenvalue Problem
E. I., J. H. Wilkinson · Mathematics of Computation · 1966 · 5.2K citations
A First Course in Numerical Analysis
Herbert Maisel, Anthony Ralston · Technometrics · 1966 · 2.5K citations
The eigenvalues of random symmetric matrices
Zoltán Füredi, János Komlós · COMBINATORICA · 1981 · 673 citations
Approximate graph coloring by semidefinite programming
David R. Karger, Rajeev Motwani, Madhu Sudan · Journal of the ACM · 1998 · 429 citations
Eigenvalues and graph bisection: An average-case analysis
Ravi B. Boppana · 1987 · 327 citations