Colouring random graphs in expected polynomial time
Please always quote using this URN:urn:nbn:de:0296-matheon-1258
- 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 suficiently large values of p, we give algorithms which approximate the chromatic number within a factor of O(?np). As a byproduct, we obtain an O(?np/ ln(np))-approximation algorithm for the independence number which runs in polynomial expected time provided p ? ln6 n/n.
Author: | Amin Coja-Oghlan, Anusch Taraz |
---|---|
URN: | urn:nbn:de:0296-matheon-1258 |
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: | 154 |