• search hit 78 of 167
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.