Online Dual Edge Coloring of Paths and Trees

Lene M. Favrholdt, Jesper With Mikkelsen

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


We study a dual version of online edge coloring, where the goal is to color as many edges as possible using only a given number, k , of available colors. All of our results are with regard to competitive analysis. For paths, we consider k=2 , and for trees, we consider any k≥2 . We prove that a natural greedy algorithm called First-Fit is optimal among deterministic algorithms on paths as well as trees. This is the first time that an optimal algorithm for online dual edge coloring has been identified for a class of graphs. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. Again, it is the first time that this has been done for a class of graphs. For trees, we also show that even randomized algorithms cannot be much better than First-Fit.
Original languageEnglish
Title of host publicationApproximation and Online Algorithms : 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers
EditorsEvripidis Bampis, Ola Svensson
Publication date2015
ISBN (Print)978-3-319-18262-9
ISBN (Electronic)978-3-319-18263-6
Publication statusPublished - 2015
EventWorkshop on Approximation and Online Algorithms - Wrocław, Poland
Duration: 11. Sept 201412. Sept 2014
Conference number: 12


ConferenceWorkshop on Approximation and Online Algorithms
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Online Dual Edge Coloring of Paths and Trees'. Together they form a unique fingerprint.

Cite this