Optimal Dynamic Distributed MIS

DOI10.1145/2933057.2933083zbMath1373.68082arXiv1507.04330OpenAlexW2223308607MaRDI QIDQ5361939

Elad Haramaty, Zohar S. Karnin, Keren Censor-Hillel

Publication date: 29 September 2017

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

Full work available at URL: https://arxiv.org/abs/1507.04330

zbMATH Keywords

randomized algorithmsmaximal independent setdynamic distributed algorithmshistory independence

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Approximation algorithms (68W25) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (6)

Some lower bounds in dynamic networks with oblivious adversaries ⋮ Average Sensitivity of Graph Algorithms ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Fully dynamic MIS in uniformly sparse graphs ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Optimal Dynamic Distributed MIS