Advice Complexity of the Online Vertex Coloring Problem
OPEN ACCESS
Author / Producer
Date
2012
Publication Type
Report
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We study online algorithms with advice for the problem of col oring graphs which come as input vertex by vertex. We consider the class of all 3-colorable graphs and its sub-classes of chordal and maximal outerplanar graphs, respectively. We show that, in the case of the first two classes, for coloring optimally, essentially log2 3 advice bits per vertex (bpv) are necessary and sufficient. In the case of maximal outerplanar graphs, we show a lower bound of 1.0424 bpv and an upper bound of 1.2932 bpv. Finally, we develop algorithms for 4-coloring in these graph classes. The al gorithm for 3 colorable chordal and outerplanar graphs uses 0.9865 bpv, and in case of general 3-colorable graphs, we obtain an algorithm using < 1.1583 bpv.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
765
Pages / Article No.
Publisher
ETH Zurich, Department of Computer Science
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03666 - Hromkovic, Juraj (emeritus) / Hromkovic, Juraj (emeritus)
02150 - Dep. Informatik / Dep. of Computer Science