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
Project funding
Redes troncales y de acceso Inteligentes Definidas por Software
Repository
http://hdl.handle.net/2117/177333 Open in new window
URL
https://www.worldscientific.com/doi/abs/10.1142/S0129054118410058 Open in new window
Abstract
Electronic version of an article published as Online graph coloring against a randomized adversary. "International journal of foundations of computer science", 1 Juny 2018, vol. 29, núm. 4, p. 551-569. DOI:10.1142/S0129054118410058 © 2018 copyright World Scientific Publishing Company. https://www.worldscientific.com/doi/abs/10.1142/S0129054118410058 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 ad...
Citation
Burjons, E. [et al.]. Online graph coloring against a randomized adversary. "International journal of foundations of computer science", 1 Juny 2018, vol. 29, núm. 4, p. 551-569.
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)

Attachments