Loosely-stabilizing maximal independent set algorithms with unreliable communications

DOI10.1016/j.tcs.2022.09.031OpenAlexW4297373176MaRDI QIDQ2089676

Toshimitsu Masuzawa, Rongcheng Dong, Taisuke Izumi, Yuichi Sudo

Publication date: 24 October 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.09.031

zbMATH Keywords

maximal independent setloose-stabilizationprobabilistically erroneous communications

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Loosely-stabilizing leader election in a population protocol model
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Quasi-self-stabilization of a distributed system assuming read/write atomicity
• Self-stabilization over unreliable communication media
• Stabilizing data-link over non-FIFO channels with optimal fault-resilience
• Loosely-stabilizing leader election with polylogarithmic convergence time
• Making randomized algorithms self-stabilizing
• The Locality of Distributed Symmetry Breaking
• On Space and Time Complexity of Loosely-Stabilizing Leader Election
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Self-stabilizing systems in spite of distributed control
• Polylogarithmic-time deterministic network decomposition and distributed derandomization

This page was built for publication: Loosely-stabilizing maximal independent set algorithms with unreliable communications