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

RIZZI, ROMEO
2001

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.
distributed computing; sparse networks; maximal independent set; maximal matching; vertex colouring; edge colouring
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: http://hdl.handle.net/11562/409608
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 120
  • ???jsp.display-item.citation.isi??? 95
social impact