Title :
Randomized online graph coloring
Author :
Vishwanathan, Sundar
Author_Institution :
Dept. of Comput. Sci., Chicago Univ., IL, USA
Abstract :
It is shown that randomization helps in coloring graphs online, and a simple randomized online algorithm is presented. For 3-colorable graphs the expected number of colors the algorithm uses is O(( n log n)1/2). The algorithm runs in polynomial time and compares well with the best known polynomial-time offline algorithms. A lower bound is proved for the randomized algorithm
Keywords :
graph colouring; 3-colorable graphs; lower bound; offline algorithms; polynomial time; randomised online graph colouring; Computer science; Legged locomotion; Polynomials; Tree graphs; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89567
