Showing 2014Show all
3 papers · 1 filter
cs.DS2014
Optimal Online Edge Coloring of Planar Graphs with Advice
Jesper W. Mikkelsen
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 f…
cs.DS2014
The Advice Complexity of a Class of Hard Online Problems
Joan Boyar, Lene M. Favrholdt, Christian Kudahl +1
The advice complexity of an online problem is a measure of how much knowledge of the future an online algorithm needs in order to achieve a certain competitive ratio. Using advice…
cs.DS2014
Online Edge Coloring of Paths and Trees with a Fixed Number of Colors
Lene M. Favrholdt, Jesper W. Mikkelsen
We study a version of online edge coloring, where the goal is to color as many edges as possible using only a given number, , of available colors. All of our results are with re…