Summary.
We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most \(2\Delta-1\) colours, and maximal matchings can be computed within \({\cal O}(\log^* n + \Delta)\) deterministic rounds, where \(\Delta\) is the maximum degree of the network. We also show how to find maximal independent sets and \((\Delta+1)\)-vertex colourings within \({\cal O}(\log^* n + \Delta^2)\) deterministic rounds. All hidden constants are very small and the algorithms are very simple.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: August 2000 / Accepted: November 2000
Rights and permissions
About this article
Cite this article
Panconesi, A., Rizzi, R. Some simple distributed algorithms for sparse networks. Distrib Comput 14, 97–100 (2001). https://doi.org/10.1007/PL00008932
Issue Date:
DOI: https://doi.org/10.1007/PL00008932