ONLINE COLORING OF SPARSE RANDOM GRAPHS AND RANDOM TREES

Authors
PITTEL B WEISHAAR RS
Citation
B. Pittel et Rs. Weishaar, ONLINE COLORING OF SPARSE RANDOM GRAPHS AND RANDOM TREES, Journal of algorithms, 23(1), 1997, pp. 195-205
Citations number
11
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
23
Issue
1
Year of publication
1997
Pages
195 - 205
Database
ISI
SICI code
0196-6774(1997)23:1<195:OCOSRG>2.0.ZU;2-B
Abstract
The performance of the greedy coloring algorithm ''first fit'' on spar se random graphs G(n,c/n) and on random trees is investigated. In each case, approximately log(2)log n colors are used, the exact number bei ng concentrated almost surely on at most two consecutive integers for a sparse random graph and on at most three consecutive integers for a random tree. (C) 1997 Academic Press.