### 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 language | English |
---|---|

Title of host publication | Euro-Par 2004 Parallel Processing |

Subtitle of host publication | 10th International Euro-Par Conference, Pisa, Italy, August 31- September 3, 2004. Proceedings |

Pages | 804-811 |

Number of pages | 8 |

Volume | 3149 |

ISBN (Electronic) | 978-3-540-27866-5 |

DOIs | |

Publication status | Published - 2004 |

Event | 10th International Euro-Par Conference - Pisa, Italy Duration: 31 Aug 2004 → 3 Sep 2004 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 3149 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | 10th International Euro-Par Conference |
---|---|

Country | Italy |

City | Pisa |

Period | 31/08/04 → 3/09/04 |

### Fingerprint

### Cite this

*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

}

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

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