Optimal Online Edge Coloring of Planar Graphs with Advice

Jesper With Mikkelsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationAlgorithms and Complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings
EditorsVangelis Th. Paschos, Peter Widmayer
PublisherSpringer
Publication date2015
Pages352-364
ISBN (Print)978-3-319-18172-1
ISBN (Electronic)978-3-319-18173-8
DOIs
Publication statusPublished - 2015
EventCIAC 2015: 9th International Conference on Algorithms and Complexity - Paris, France
Duration: 20. May 201522. May 2015

Conference

ConferenceCIAC 2015
Country/TerritoryFrance
CityParis
Period20/05/201522/05/2015
SeriesLecture Notes in Computer Science
Volume9079
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Optimal Online Edge Coloring of Planar Graphs with Advice'. Together they form a unique fingerprint.

Cite this