Online Dual Edge Coloring of Paths and Trees

Lene M. Favrholdt; Jesper With Mikkelsen

doi:10.1007/978-3-319-18263-6_16

Online Dual Edge Coloring of Paths and Trees

Lene M. Favrholdt, Jesper With Mikkelsen

Institut for Matematik og Datalogi

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

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.

Originalsprog	Engelsk
Titel	Approximation and Online Algorithms : 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers
Redaktører	Evripidis Bampis, Ola Svensson
Forlag	Springer
Publikationsdato	2015
Sider	181-192
ISBN (Trykt)	978-3-319-18262-9
ISBN (Elektronisk)	978-3-319-18263-6
DOI	https://doi.org/10.1007/978-3-319-18263-6_16
Status	Udgivet - 2015
Begivenhed	Workshop on Approximation and Online Algorithms - Wrocław, Polen Varighed: 11. sep. 2014 → 12. sep. 2014 Konferencens nummer: 12

Konference

Konference	Workshop on Approximation and Online Algorithms
Nummer	12
Land/Område	Polen
By	Wrocław
Periode	11/09/2014 → 12/09/2014

Navn	Lecture Notes in Computer Science
Vol/bind	8952
ISSN	0302-9743

Dokumenter og links

10.1007/978-3-319-18263-6_16

Citationsformater

Favrholdt, L. M., & Mikkelsen, J. W. (2015). Online Dual Edge Coloring of Paths and Trees. I E. Bampis, & O. Svensson (red.), Approximation and Online Algorithms: 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers (s. 181-192). Springer. Lecture Notes in Computer Science Bind 8952 https://doi.org/10.1007/978-3-319-18263-6_16

@inproceedings{d1d497ef61cf4eac95fc5cd55b1f3555,

title = "Online Dual Edge Coloring of Paths and Trees",

abstract = "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.",

author = "Favrholdt, {Lene M.} and Mikkelsen, {Jesper With}",

year = "2015",

doi = "10.1007/978-3-319-18263-6_16",

language = "English",

isbn = "978-3-319-18262-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "181--192",

editor = "Evripidis Bampis and Ola Svensson",

booktitle = "Approximation and Online Algorithms",

address = "Germany",

note = "Workshop on Approximation and Online Algorithms, WAOA 2014 ; Conference date: 11-09-2014 Through 12-09-2014",

}

Favrholdt, LM & Mikkelsen, JW 2015, Online Dual Edge Coloring of Paths and Trees. i E Bampis & O Svensson (red), Approximation and Online Algorithms: 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers. Springer, Lecture Notes in Computer Science, bind 8952, s. 181-192, Workshop on Approximation and Online Algorithms, Wrocław, Polen, 11/09/2014. https://doi.org/10.1007/978-3-319-18263-6_16

Online Dual Edge Coloring of Paths and Trees. / Favrholdt, Lene M.; Mikkelsen, Jesper With.

Approximation and Online Algorithms: 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers. red. / Evripidis Bampis; Ola Svensson. Springer, 2015. s. 181-192 (Lecture Notes in Computer Science, Bind 8952).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Online Dual Edge Coloring of Paths and Trees

AU - Favrholdt, Lene M.

AU - Mikkelsen, Jesper With

N1 - Conference code: 12

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-18263-6_16

DO - 10.1007/978-3-319-18263-6_16

M3 - Article in proceedings

SN - 978-3-319-18262-9

T3 - Lecture Notes in Computer Science

SP - 181

EP - 192

BT - Approximation and Online Algorithms

A2 - Bampis, Evripidis

A2 - Svensson, Ola

PB - Springer

T2 - Workshop on Approximation and Online Algorithms

Y2 - 11 September 2014 through 12 September 2014

ER -

Online Dual Edge Coloring of Paths and Trees

Abstract

Konference

Dokumenter og links

Fingeraftryk

Citationsformater