Loading...
Loading...

Go to the content (press return)

Online graph coloring against a randomized adversary

Author
Burjons, E.; Hromkovic, J.; Kralovic, R.; Muñoz, X.; Unger, W.
Type of activity
Journal article
Journal
International journal of foundations of computer science
Date of publication
2018-06-01
Volume
29
Number
4
First page
551
Last page
569
DOI
10.1142/S0129054118410058
URL
https://www.worldscientific.com/doi/abs/10.1142/S0129054118410058 Open in new window
Abstract
We consider an online model where an adversary constructs a set of 2s instances S instead of one single instance. The algorithm knows S and the adversary will choose one instance from S at random to present to the algorithm. We further focus on adversaries that construct sets of k-chromatic instances. In this setting, we provide upper and lower bounds on the competitive ratio for the online graph coloring problem as a function of the parameters in this model. Both bounds are linear in s and matc...
Keywords
Online computation, graph coloring, information, randomization
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants

  • Burjons Pujol, Elisabet  (author)
  • Hromkovic, Juraj  (author)
  • Kralovic, Rastislav  (author)
  • Kralovic, Richard  (author)
  • Muñoz Lopez, Francisco Javier  (author)
  • Unger, Walter  (author)