New self-stabilizing algorithms for minimal weakly connected dominating sets

DOI10.1142/S0129054115500136MaRDI QIDQ5261609zbMATH OpenOpenAlexFDO

Authors Yihua Ding, James Z. Wang, Pradip K. Srimani

Publication date 6 July 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054115500136

zbMATH Keywords

self-stabilizationcentral daemondistributed daemonminimal weakly connected dominating set

Mathematics Subject Classification ID

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

Recommendations

• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Self-stabilizing algorithm for minimal dominating set with safe convergence in an arbitrary graph
• Efficient self-stabilizing algorithms for minimal total \(k\)-dominating sets in graphs
• Linear-time self-stabilizing algorithms for minimal domination in graphs

Cites work

• A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
• A self-stabilizing distributed approximation algorithm for the minimum connected dominating set
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Self-stabilizing systems in spite of distributed control

Cited in

(15)

• Self-Stabilizing Domination Algorithms
• A self-stabilizing distributed approximation algorithm for the minimum connected dominating set
• A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Learning automata-based algorithms for finding minimum weakly connected dominating set in stochastic graphs
• A \(4n\)-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon
• Enabling minimal dominating set in highly dynamic distributed systems
• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
• An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs
• 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
• Self-stabilizing algorithm for minimal dominating set with safe convergence in an arbitrary graph
• Self-stabilizing algorithm for two disjoint minimal dominating sets
• Distributed Computing - IWDC 2003

This page was built for publication: New self-stabilizing algorithms for minimal weakly connected dominating sets

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