Name
Abstract | ||
|---|---|---|
We investigate the problem of colouring random graphs G 驴 G(n, p) in polynomial expected time. For the case p n, we present an algorithm that finds an optimal colouring in linear expected time. For sufficiently 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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/3-540-36494-3_43 | STACS |
Keywords | Field | DocType |
random graph,linear expected time,polynomial expected time,colouring random graphs,optimal colouring,chromatic number,large value,approximation algorithm,independence number,ln6 n,expected polynomial time,case p n,polynomial time | Approximation algorithm,Discrete mathematics,Pseudo-polynomial time,Combinatorics,Independence number,Random graph,Polynomial,Greedy algorithm,Time complexity,Minimum time,Mathematics | Conference |
Volume | ISSN | ISBN |
2607 | 0302-9743 | 3-540-00623-0 |
Citations | PageRank | References |
10 | 0.83 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amin Coja-Oghlan | 1 | 543 | 47.25 |
| Anusch Taraz | 2 | 168 | 37.71 |