A 4n-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon

DOI10.1016/J.IPL.2014.04.011MaRDI QIDQ2015142zbMATH OpenOpenAlexFDO

Authors Well Y. Chiu, Chiuyuan Chen, Shih-Yu Tsai

Publication date 23 June 2014

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

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

zbMATH Keywords

distributed computinggraph algorithmdominationfault toleranceself-stabilizing algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14)

Recommendations

• Linear-time self-stabilizing algorithms for minimal domination in graphs
• Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler
• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
• New self-stabilizing algorithms for minimal weakly connected dominating sets
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
• Distance-\(k\) knowledge in self-stabilizing algorithms
• Distributed Computing - IWDC 2003
• Efficient transformation of distance-2 self-stabilizing algorithms
• Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler
• Linear-time self-stabilizing algorithms for minimal domination in graphs
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Self-stabilizing systems in spite of distributed control

Cited in

(11)

• Self-Stabilizing Domination Algorithms
• Self-stabilizing 2-minimal dominating set algorithms based on loop composition
• Brief announcement: Fully lattice linear algorithms
• Extending Lattice Linearity for Self-stabilizing Algorithms
• Short correctness proofs for two self-stabilizing algorithms under the distributed daemon model
• A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs
• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
• Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler
• Linear-time self-stabilizing algorithms for minimal domination in graphs
• A self-stabilizing algorithm for finding a minimal 2-dominating set assuming the distributed demon model
• Efficient self-stabilizing algorithm for independent strong dominating sets in arbitrary graphs

This page was built for publication: A \(4n\)-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon

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