We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most 2D-1 colours, and maximal matchings can be computed within O(log^* n + D) deterministic rounds, where D is the maximum degree of the network. We also show how to find maximal independent sets and (D+1)-vertex colourings within O(log^* n + D^2) deterministic rounds. All hidden constants are very small and the algorithms are very simple.

Some Simple Distributed Algorithms for Sparse Networks / Panconesi, Alessandro; Rizzi, Romeo. - ELETTRONICO. - (2001), pp. 1-7.

Some Simple Distributed Algorithms for Sparse Networks

Rizzi, Romeo
2001-01-01

Abstract

We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most 2D-1 colours, and maximal matchings can be computed within O(log^* n + D) deterministic rounds, where D is the maximum degree of the network. We also show how to find maximal independent sets and (D+1)-vertex colourings within O(log^* n + D^2) deterministic rounds. All hidden constants are very small and the algorithms are very simple.
2001
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Some Simple Distributed Algorithms for Sparse Networks / Panconesi, Alessandro; Rizzi, Romeo. - ELETTRONICO. - (2001), pp. 1-7.
Panconesi, Alessandro; Rizzi, Romeo
File in questo prodotto:
File Dimensione Formato  
39.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 661.23 kB
Formato Adobe PDF
661.23 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/358460
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact