A self-stabilizing algorithm for constructing weakly connected minimal dominating sets

DOI10.1016/J.IPL.2009.03.013MaRDI QIDQ989481zbMATH OpenOpenAlexFDO

Authors Volker Turau, Bernd Hauck

Publication date 20 August 2010

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

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

zbMATH Keywords

distributed algorithmsgraph algorithmsfault toleranceself-stabilizing algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 2079403 (Why is no real title available?)
• A self-stabilizing algorithm for constructing breadth-first trees
• Distance-\(k\) knowledge in self-stabilizing algorithms
• Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• On weakly connected domination in graphs
• Self-stabilization

Cited in

(12)

• Self-Stabilizing Domination Algorithms
• Self-stabilizing algorithms for minimal global powerful alliance sets in graphs
• A self-stabilizing distributed approximation algorithm for the minimum connected dominating set
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Brief announcement: Fully lattice linear algorithms
• A silent self-stabilizing algorithm for the generalized minimal k-dominating set problem
• An \(O(n^2)\) self-stabilizing algorithm for computing bridge-connected components
• A \(4n\)-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon
• Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler
• New self-stabilizing algorithms for minimal weakly connected dominating sets
• A self-stabilizing algorithm for finding a minimal 2-dominating set assuming the distributed demon model
• Finding minimum weight connected dominating set in stochastic graph based on learning automata

This page was built for publication: A self-stabilizing algorithm for constructing weakly connected minimal dominating sets

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