Distributed MIS via All-to-All Communication

DOI10.1145/3087801.3087830zbMath1380.68424OpenAlexW2739022923MaRDI QIDQ5368954

Mohsen Ghaffari

Publication date: 11 October 2017

Published in: Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3087801.3087830

zbMATH Keywords

distributed graph algorithmscongested cliquemaximal independent set (MIS)

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (10)

Graph reconstruction in the congested clique ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Distributed Self-Stabilizing MIS with Few States and Weak Communication ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds ⋮ Fast approximate shortest paths in the congested clique ⋮ Near-optimal scheduling in the congested clique

This page was built for publication: Distributed MIS via All-to-All Communication