Loosely-stabilizing maximal independent set algorithms with unreliable communications

DOI10.1016/J.TCS.2022.09.031MaRDI QIDQ2089676zbMATH OpenOpenAlexFDO

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

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

loose-stabilizationmaximal independent setprobabilistically erroneous communications

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
• Luby's MIS algorithms made self-stabilizing
• Self-stabilization over unreliable communication media
• Making randomized algorithms self-stabilizing
• A self-stabilizing 1-maximal independent set algorithm

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
• Loosely-stabilizing leader election with polylogarithmic convergence time
• Making randomized algorithms self-stabilizing
• On space and time complexity of loosely-stabilizing leader election
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Quasi-self-stabilization of a distributed system assuming read/write atomicity
• 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

(2)

• Distributed Maximal Independent Set using Small Messages
• Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications

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 Q2089676)