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

Department of Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › 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.

Original language	English
Title of host publication	Approximation and Online Algorithms : 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers
Editors	Evripidis Bampis, Ola Svensson
Publisher	Springer
Publication date	2015
Pages	181-192
ISBN (Print)	978-3-319-18262-9
ISBN (Electronic)	978-3-319-18263-6
DOIs	https://doi.org/10.1007/978-3-319-18263-6_16
Publication status	Published - 2015
Event	Workshop on Approximation and Online Algorithms - Wrocław, Poland Duration: 11. Sept 2014 → 12. Sept 2014 Conference number: 12

Conference

Conference	Workshop on Approximation and Online Algorithms
Number	12
Country/Territory	Poland
City	Wrocław
Period	11/09/2014 → 12/09/2014

Series	Lecture Notes in Computer Science
Volume	8952
ISSN	0302-9743

Documents & Links

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

SDU Link

Check access to the material in SDU Library's search engine

Cite this

@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. in E Bampis & O Svensson (eds), Approximation and Online Algorithms: 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers. Springer, Lecture Notes in Computer Science, vol. 8952, pp. 181-192, Workshop on Approximation and Online Algorithms, Wrocław, Poland, 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. ed. / Evripidis Bampis; Ola Svensson. Springer, 2015. p. 181-192 (Lecture Notes in Computer Science, Vol. 8952).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › 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

Conference

Documents & Links

SDU Link

Fingerprint

Cite this