id: 06044345
dt: a
an: 06044345
au: Forišek, Michal; Keller, Lucia; Steinová, Monika
ti: Advice complexity of online coloring for paths.
so: Dediu, Adrian-Horia (ed.) et al., Language and automata theory and
    applications. 6th international conference, LATA 2012, A Coruña,
    Spain, March 5‒9, 2012. Proceedings. Berlin: Springer (ISBN
    978-3-642-28331-4/pbk). Lecture Notes in Computer Science 7183, 228-239
    (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: Advice Complexity; Online Graph Coloring; Partial Coloring
ci: 
li: doi:10.1007/978-3-642-28332-1_20
ab: Summary: In online graph coloring a graph is revealed to an online
    algorithm one vertex at a time, and the algorithm must color the
    vertices as they appear. This paper starts to investigate the advice
    complexity of this problem ‒ the amount of oracle information an
    online algorithm needs in order to make optimal choices. We also
    consider a more general problem ‒ a trade-off between online and
    offline graph coloring. In the paper we prove that precisely $\lceil
    n/2 \rceil - 1$ bits of advice are needed when the vertices on a path
    are presented for coloring in arbitrary order. The same holds in the
    more general case when just a subset of the vertices is colored online.
    However, the problem turns out to be non-trivial for the case where the
    online algorithm is guaranteed that the vertices it receives form a
    subset of a path and are presented in the order in which they lie on
    the path. For this variant we prove that its advice complexity is $βn
    + O(\log n)$ bits, where $β\approx 0.406$ is a fixed constant (we give
    its closed form). This suggests that the generalized problem will be
    challenging for more complex graph classes.
rv: