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
T2 - 10th International Euro-Par Conference
Y2 - 31 August 2004 through 3 September 2004
ER -