Some simple distributed algorithms for sparse networks |
| |
Authors: | Alessandro Panconesi Romeo Rizzi |
| |
Affiliation: | DSI, Universitá La Sapienza di Roma, Via Salaria 113, 00198 Roma, Italy, IT BRICS, University of ?rhus, 8000 ?rhus C, Denmark, DK
|
| |
Abstract: | Summary. We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most colours, and maximal matchings can be computed within deterministic rounds, where is the maximum degree of the network. We also show how to find maximal independent sets and -vertex colourings within deterministic rounds. All hidden constants are very small and the algorithms are very simple. Received: August 2000 / Accepted: November 2000 |
| |
Keywords: | : Distributed computing – Sparse networks – Maximal independent set – Maximal matching – Vertex colouring – Edge colouring |
本文献已被 SpringerLink 等数据库收录! |
|