Luby's MIS algorithms made self-stabilizing

DOI10.1016/J.IPL.2024.106531MaRDI QIDQ6663516zbMATH OpenFDO

Authors George Giakkoupis, Volker Turau, Isabella Ziccardi

Publication date 14 January 2025

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2024.106531

zbMATH Keywords

distributed computingfault tolerancemaximal independent set (MIS)self-stabilization

Mathematics Subject Classification ID

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

Recommendations

• Making randomized algorithms self-stabilizing
• An optimal bit complexity randomized distributed MIS algorithm
• A self-stabilizing 1-maximal independent set algorithm
• An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
• Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
• A Thin Self-Stabilizing Asynchronous Unison Algorithm with Applications to Fault Tolerant Biological Networks
• An optimal bit complexity randomized distributed MIS algorithm
• Deploying wireless networks with beeps
• Distributed Self-Stabilizing MIS with Few States and Weak Communication
• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 7788511 (Why is no real title available?)
• Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler
• Local stabilizer
• Locally-iterative Distributed (Δ + 1)-coloring and Applications
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• Self-stabilization
• Self-stabilizing systems in spite of distributed control
• The locality of distributed symmetry breaking
• Time optimal self-stabilizing synchronization

Cited in

(4)

• Loosely-stabilizing maximal independent set algorithms with unreliable communications
• Making randomized algorithms self-stabilizing
• A self-stabilizing 1-maximal independent set algorithm
• Self-stabilizing MIS computation in the beeping model

This page was built for publication: Luby's MIS algorithms made self-stabilizing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6663516)