Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler

DOI10.1016/J.IPL.2007.02.013MaRDI QIDQ2379950zbMATH OpenOpenAlexFDO

Authors Volker Turau

Publication date 24 March 2010

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

Full work available at URL https://doi.org/10.1016/j.ipl.2007.02.013

zbMATH Keywords

distributed computinggraph algorithmsfault toleranceself-stabilizing algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Distributed systems (68M14)

Recommendations

• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• A \(4n\)-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon
• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
• Linear-time self-stabilizing algorithms for minimal domination in graphs
• Efficient self-stabilizing algorithms for minimal total \(k\)-dominating sets in graphs

Cites work

• scientific article; zbMATH DE number 1919504 (Why is no real title available?)
• Distributed Computing - IWDC 2003
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• Self-stabilization
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Self-stabilizing systems in spite of distributed control

Cited in

(19)

• Self-Stabilizing Domination Algorithms
• Self-stabilizing algorithms for minimal global powerful alliance sets in graphs
• Efficient transformation of distance-2 self-stabilizing algorithms
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
• Self-stabilizing 2-minimal dominating set algorithms based on loop composition
• Fast, silent self-stabilizing distance-\(k\) independent dominating set construction
• Brief announcement: Fully lattice linear algorithms
• A \(4n\)-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon
• Extending Lattice Linearity for Self-stabilizing Algorithms
• A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2
• scientific article; zbMATH DE number 1863300 (Why is no real title available?)
• Resource efficient stabilization for local tasks despite unknown capacity links
• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
• Distributed Self-Stabilizing MIS with Few States and Weak Communication
• Efficient self-stabilizing algorithm for independent strong dominating sets in arbitrary graphs
• Luby's MIS algorithms made self-stabilizing
• Self-stabilizing distributed algorithm for local mutual inclusion
• A self-stabilizing 1-maximal independent set algorithm
• Self-stabilizing algorithms for unfriendly partitions into two disjoint dominating sets

This page was built for publication: Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler

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