• search hit 10 of 28
Back to Result List

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.

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