Exact and approximative algorithms for colouring G(n,p)
Please always quote using this URN:urn:nbn:de:0296-matheon-1246
- 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.
Author: | Amin Coja-Oghlan, Anusch Taraz |
---|---|
URN: | urn:nbn:de:0296-matheon-1246 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2004/09/19 |
Release Date: | 2004/04/19 |
Institute: | Humboldt-Universität zu Berlin |
Preprint Number: | 153 |