CATALOGO DEI PRODOTTI DELLA RICERCA
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe 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.
| Titolo: | Some Simple Distributed Algorithms for Sparse Networks | |
| Autori: | ||
| Data di pubblicazione: | 2001 | |
| Rivista: | ||
| 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. | |
| Handle: | http://hdl.handle.net/11562/409608 | |
| Appare nelle tipologie: | 01.01 Articolo in Rivista |
File in questo prodotto:
http://hdl.handle.net/11562/409608
Copyright © 2022