Distributed MIS with Low Energy and Time Complexities

DOI10.1145/3583668.3594587arXiv2305.11639MaRDI QIDQ6202237

Unnamed Author, Mohsen Ghaffari

Publication date: 26 March 2024

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

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

zbMATH Keywords

distributed algorithmsmaximal independent setenergy-efficiencyround complexityenergy complexityMISawake complexitysleeping modelworst-case energy complexity

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Local Computation
• The Locality of Distributed Symmetry Breaking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• Exponential separations in the energy complexity of leader election
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Efficient algorithms for leader election in radio networks
• The Energy Complexity of Broadcast
• Distributed Maximal Independent Set using Small Messages
• Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity
• The Energy Complexity of BFS in Radio Networks