TY - GEN

T1 - Optimal Online Edge Coloring of Planar Graphs with Advice

AU - Mikkelsen, Jesper With

PY - 2015

Y1 - 2015

N2 - Using the framework of advice complexity, we study the amount of knowledge about the future that an online algorithm needs to color the edges of a graph optimally, i.e., using as few colors as possible. For graphs of maximum degree Δ , it follows from Vizing’s Theorem that O(mlogΔ) bits of advice suffice to achieve optimality, where m is the number of edges. We show that for graphs of bounded degeneracy (a class of graphs including e.g. trees and planar graphs), only O(m) bits of advice are needed to compute an optimal solution online, independently of how large Δ is. On the other hand, we show that Ω(m) bits of advice are necessary just to achieve a competitive ratio better than that of the best deterministic online algorithm without advice. Furthermore, we consider algorithms which use a fixed number of advice bits per edge (our algorithm for graphs of bounded degeneracy belongs to this class of algorithms). We show that for bipartite graphs, any such algorithm must use at least Ω(mlogΔ) bits of advice to achieve optimality.

AB - Using the framework of advice complexity, we study the amount of knowledge about the future that an online algorithm needs to color the edges of a graph optimally, i.e., using as few colors as possible. For graphs of maximum degree Δ , it follows from Vizing’s Theorem that O(mlogΔ) bits of advice suffice to achieve optimality, where m is the number of edges. We show that for graphs of bounded degeneracy (a class of graphs including e.g. trees and planar graphs), only O(m) bits of advice are needed to compute an optimal solution online, independently of how large Δ is. On the other hand, we show that Ω(m) bits of advice are necessary just to achieve a competitive ratio better than that of the best deterministic online algorithm without advice. Furthermore, we consider algorithms which use a fixed number of advice bits per edge (our algorithm for graphs of bounded degeneracy belongs to this class of algorithms). We show that for bipartite graphs, any such algorithm must use at least Ω(mlogΔ) bits of advice to achieve optimality.

U2 - 10.1007/978-3-319-18173-8_26

DO - 10.1007/978-3-319-18173-8_26

M3 - Article in proceedings

SN - 978-3-319-18172-1

T3 - Lecture Notes in Computer Science

SP - 352

EP - 364

BT - Algorithms and Complexity

A2 - Th. Paschos, Vangelis

A2 - Widmayer, Peter

PB - Springer

T2 - CIAC 2015

Y2 - 20 May 2015 through 22 May 2015

ER -