Online Graph Coloring Against a Randomized Adversary

DOI10.1142/S0129054118410058zbMath1397.68229MaRDI QIDQ3177338

Juraj Hromkovič, Xavier Muñoz, Walter Unger, Rastislav Královič, Richard Královič, Elisabet Burjons

Publication date: 24 July 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

randomization; information; graph coloring; online computation

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

68W20: Randomized algorithms

68W27: Online algorithms; streaming algorithms