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)peer-review

11 Citations (Scopus)


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
Number of pages8
ISBN (Electronic)978-3-540-27866-5
Publication statusPublished - 2004
Event10th International Euro-Par Conference - Pisa, Italy
Duration: 31 Aug 20043 Sep 2004

Publication series

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


Conference10th International Euro-Par Conference

Fingerprint Dive into the research topics of 'Distributed largest-first algorithm for graph coloring'. Together they form a unique fingerprint.

Cite this