Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications

DOI10.1007/978-3-030-91081-5_22MaRDI QIDQ6488445zbMATH OpenFDO

Authors Rongcheng Dong, Yuichi Sudo, Taisuke Izumi, Toshimitsu Masuzawa

Publication date 21 April 2023

Full work available at URL https://doi.org/10.1007/978-3-030-91081-5_22

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Loosely-stabilizing maximal independent set algorithms with unreliable communications
• An Improved Distributed Algorithm for Maximal Independent Set
• Distributed Reconfiguration of Maximal Independent Sets
• Distributed reconfiguration of maximal independent sets
• Improved distributed approximations for maximum independent set
• Distributed Maximal Independent Set using Small Messages
• Distributed approximation of maximum independent set and maximum matching
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets

Cites work

• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• scientific article; zbMATH DE number 2036573 (Why is no real title available?)
• Loosely-stabilizing leader election in a population protocol model
• Making randomized algorithms self-stabilizing
• On space and time complexity of loosely-stabilizing leader election
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Self-stabilization over unreliable communication media
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Self-stabilizing systems in spite of distributed control
• Stabilizing data-link over non-FIFO channels with optimal fault-resilience
• The locality of distributed symmetry breaking

Cited in

(3)

• Loosely-stabilizing maximal independent set algorithms with unreliable communications
• Distributed Maximal Independent Set using Small Messages
• Luby's MIS algorithms made self-stabilizing

This page was built for publication: Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications

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