Online Dual Edge Coloring of Paths and Trees

Lene M. Favrholdt, Jesper With Mikkelsen

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
TitelApproximation and Online Algorithms : 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers
RedaktørerEvripidis Bampis, Ola Svensson
ForlagSpringer
Publikationsdato2015
Sider181-192
ISBN (Trykt)978-3-319-18262-9
ISBN (Elektronisk)978-3-319-18263-6
DOI
StatusUdgivet - 2015
BegivenhedWorkshop on Approximation and Online Algorithms - Wrocław, Polen
Varighed: 11. sep. 201412. sep. 2014
Konferencens nummer: 12

Konference

KonferenceWorkshop on Approximation and Online Algorithms
Nummer12
LandPolen
ByWrocław
Periode11/09/201412/09/2014
NavnLecture Notes in Computer Science
Vol/bind8952
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'Online Dual Edge Coloring of Paths and Trees'. Sammen danner de et unikt fingeraftryk.

Citationsformater