Exact and approximative algorithms for coloring G(n,p)
Amin Coja‐Oghlan, Anusch Taraz · Random Structures and Algorithms · 2004
Abstract We investigate the problem of coloring random graphs G ( n, p ) in polynomial expected time. For the case p ≤ 1.01/ n , we present an algorithm that finds an optimal coloring in linear expected time. For p ≫ ln 6 ( n )/ n , we give algorithms which approximate the chromatic number within a factor of O ( ). We also obtain an O (/ln( np ))‐approximation algorithm for the independence number. As an application, we propose an algorithm for deciding satisfiability of random 2 k ‐SAT formulas over n propositional variables with ≥ ln 7 ( n ) n k clauses in polynomial expected time. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004