Distributed largest-first algorithm for graph coloring

Jennie Hansen, Marek Kubale, Łukasz Kuszner, Adam Nadolski

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

Abstract

In the paper we present a distributed probabilistic algorithm for coloring the vertices of a graph. Since this algorithm resembles a largest-first strategy, we call it the distributed LF (DLF) algorithm. The coloring obtained by DLF is optimal or near optimal for numerous classes of graphs e.g. complete ?-partite, caterpillars, crowns, bipartite wheels. We also show that DLF runs in O(?2 log n) rounds for an arbitrary graph, where n is the number of vertices and ? denotes the largest vertex degree. © Springer-Verlag 2004.

Original languageEnglish
Title of host publicationEuro-Par 2004 Parallel Processing
Subtitle of host publication10th International Euro-Par Conference, Pisa, Italy, August 31- September 3, 2004. Proceedings
Pages804-811
Number of pages8
Volume3149
ISBN (Electronic)978-3-540-27866-5
DOIs
Publication statusPublished - 2004
Event10th International Euro-Par Conference - Pisa, Italy
Duration: 31 Aug 20043 Sep 2004

Publication series

NameLecture Notes in Computer Science
Volume3149
ISSN (Print)0302-9743

Conference

Conference10th International Euro-Par Conference
CountryItaly
CityPisa
Period31/08/043/09/04

Fingerprint

Coloring
Parallel algorithms
Wheels

Cite this

Hansen, J., Kubale, M., Kuszner, Ł., & Nadolski, A. (2004). Distributed largest-first algorithm for graph coloring. In Euro-Par 2004 Parallel Processing: 10th International Euro-Par Conference, Pisa, Italy, August 31- September 3, 2004. Proceedings (Vol. 3149, pp. 804-811). (Lecture Notes in Computer Science; Vol. 3149). https://doi.org/10.1007/978-3-540-27866-5_107
Hansen, Jennie ; Kubale, Marek ; Kuszner, Łukasz ; Nadolski, Adam. / Distributed largest-first algorithm for graph coloring. Euro-Par 2004 Parallel Processing: 10th International Euro-Par Conference, Pisa, Italy, August 31- September 3, 2004. Proceedings. Vol. 3149 2004. pp. 804-811 (Lecture Notes in Computer Science).
@inbook{f61c2fd0cee84e7fb391f1da3155b85e,
title = "Distributed largest-first algorithm for graph coloring",
abstract = "In the paper we present a distributed probabilistic algorithm for coloring the vertices of a graph. Since this algorithm resembles a largest-first strategy, we call it the distributed LF (DLF) algorithm. The coloring obtained by DLF is optimal or near optimal for numerous classes of graphs e.g. complete ?-partite, caterpillars, crowns, bipartite wheels. We also show that DLF runs in O(?2 log n) rounds for an arbitrary graph, where n is the number of vertices and ? denotes the largest vertex degree. {\circledC} Springer-Verlag 2004.",
author = "Jennie Hansen and Marek Kubale and Łukasz Kuszner and Adam Nadolski",
year = "2004",
doi = "10.1007/978-3-540-27866-5_107",
language = "English",
isbn = "978-3-540-22924-7",
volume = "3149",
series = "Lecture Notes in Computer Science",
pages = "804--811",
booktitle = "Euro-Par 2004 Parallel Processing",

}

Hansen, J, Kubale, M, Kuszner, Ł & Nadolski, A 2004, Distributed largest-first algorithm for graph coloring. in Euro-Par 2004 Parallel Processing: 10th International Euro-Par Conference, Pisa, Italy, August 31- September 3, 2004. Proceedings. vol. 3149, Lecture Notes in Computer Science, vol. 3149, pp. 804-811, 10th International Euro-Par Conference, Pisa, Italy, 31/08/04. https://doi.org/10.1007/978-3-540-27866-5_107

Distributed largest-first algorithm for graph coloring. / Hansen, Jennie; Kubale, Marek; Kuszner, Łukasz; Nadolski, Adam.

Euro-Par 2004 Parallel Processing: 10th International Euro-Par Conference, Pisa, Italy, August 31- September 3, 2004. Proceedings. Vol. 3149 2004. p. 804-811 (Lecture Notes in Computer Science; Vol. 3149).

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

TY - CHAP

T1 - Distributed largest-first algorithm for graph coloring

AU - Hansen, Jennie

AU - Kubale, Marek

AU - Kuszner, Łukasz

AU - Nadolski, Adam

PY - 2004

Y1 - 2004

N2 - In the paper we present a distributed probabilistic algorithm for coloring the vertices of a graph. Since this algorithm resembles a largest-first strategy, we call it the distributed LF (DLF) algorithm. The coloring obtained by DLF is optimal or near optimal for numerous classes of graphs e.g. complete ?-partite, caterpillars, crowns, bipartite wheels. We also show that DLF runs in O(?2 log n) rounds for an arbitrary graph, where n is the number of vertices and ? denotes the largest vertex degree. © Springer-Verlag 2004.

AB - In the paper we present a distributed probabilistic algorithm for coloring the vertices of a graph. Since this algorithm resembles a largest-first strategy, we call it the distributed LF (DLF) algorithm. The coloring obtained by DLF is optimal or near optimal for numerous classes of graphs e.g. complete ?-partite, caterpillars, crowns, bipartite wheels. We also show that DLF runs in O(?2 log n) rounds for an arbitrary graph, where n is the number of vertices and ? denotes the largest vertex degree. © Springer-Verlag 2004.

UR - http://www.scopus.com/inward/record.url?scp=33749988268&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-27866-5_107

DO - 10.1007/978-3-540-27866-5_107

M3 - Chapter (peer-reviewed)

SN - 978-3-540-22924-7

VL - 3149

T3 - Lecture Notes in Computer Science

SP - 804

EP - 811

BT - Euro-Par 2004 Parallel Processing

ER -

Hansen J, Kubale M, Kuszner Ł, Nadolski A. Distributed largest-first algorithm for graph coloring. In Euro-Par 2004 Parallel Processing: 10th International Euro-Par Conference, Pisa, Italy, August 31- September 3, 2004. Proceedings. Vol. 3149. 2004. p. 804-811. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-540-27866-5_107