TY - GEN A1 - Coja-Oghlan, Amin A1 - Taraz, Anusch T1 - Exact and approximative algorithms for colouring G(n,p) N2 - We investigate the problem of colouring random graphs G ? G(n; p) in polynomial expected time. For the case p ? 1.01/n, we present an algorithm that finds an optimal colouring in linear expected time. For p ?? ln6(n)/n, we give algorithms which approximate the chromatic number within a factor of O(? np). We also obtain an O(? np/ ln(np))- approximation algorithm for the independence number. As an application, we propose an algorithm for deciding satisfiability of random 2k- SAT formulas (with sufficiently many clauses) in polynomial expected time. Y1 - 2004 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/124 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-1246 ER -