RANDOMIZED ONLINE GRAPH-COLORING

被引:29
作者
VISHWANATHAN, S [1 ]
机构
[1] UNIV CHICAGO,DEPT COMP SCI,CHICAGO,IL 60637
关键词
D O I
10.1016/0196-6774(92)90061-G
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by Lovász, Saks, and Trotter, (Discrete Math. 75 (1989), 319-325). Their algorithm colors graphs of chromatic number χ with no more than (2χn) log* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O( n log log log n log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2χχ2n (χ-2) (χ-1)(log n) 1 (χ-1)). For three-colorable graphs the expected number of colors our algorithm uses is O( n log n). All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to Avrim Blum, uses O(n 3 8 poly-log(n)) colors (in "Proceedings, 31st Annual Sympos. Found. Comput. Sci., 1990," pp. 554-562). We also prove a lower bound of Ω(( 1 (χ - 1))(( log n (12(χ + 1))) - 1)χ-1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω(( log n log log n)χ-1), due to Noga Alon (personal communication, September 1989). © 1992.
引用
收藏
页码:657 / 669
页数:13
相关论文
共 11 条
[1]  
ALON N, 1989, COMMUNICATION SEP
[2]  
BEAN D, 1976, J SYMBOLIC LOGIC JUN, P469
[3]  
Blum A., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P535, DOI 10.1145/73007.73058
[4]  
BLUM A, 1990, 31ST P ANN S F COMP, P554
[5]  
HALLDORSSON M, 1991, COMMUNICATION
[6]  
HALLDORSSON MM, 1991, THESIS RUTGERS STATE
[7]  
IRANI S, 1990, 31ST P S F COMP SCI, P470
[8]  
KARLOFF H, 1990, COMMUNICATION MAY
[9]   AN ONLINE GRAPH-COLORING ALGORITHM WITH SUBLINEAR PERFORMANCE RATIO [J].
LOVASZ, L ;
SAKS, M ;
TROTTER, WT .
DISCRETE MATHEMATICS, 1989, 75 (1-3) :319-325
[10]  
SZEGEDY M, 1989, COMMUNICATION MAR