Self-stabilizing algorithms for minimal dominating sets and maximal independent sets

DOI10.1016/S0898-1221(03)90143-XzbMath1043.05089MaRDI QIDQ597323

Sumit K. Garg

Publication date: 6 August 2004

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

zbMATH Keywords

Dominating setGraphIndependent setSelf-stabilizing algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14)

Related Items (16)

Efficient Self-Stabilizing Algorithm for Independent Strong Dominating Sets in Arbitrary Graphs ⋮ Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler ⋮ An anonymous self-stabilizing algorithm for 1-maximal independent set in trees ⋮ Self-stabilizing algorithm for two disjoint minimal dominating sets ⋮ Self-stabilizing 2-minimal dominating set algorithms based on loop composition ⋮ A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs ⋮ Distributed Self-Stabilizing MIS with Few States and Weak Communication ⋮ A self-stabilizing algorithm to maximal 2-packing with improved complexity ⋮ A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs ⋮ A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler ⋮ A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET ⋮ A self-stabilizing algorithm for cut problems in synchronous networks ⋮ A \(4n\)-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon ⋮ Self-Stabilizing Domination Algorithms ⋮ Loosely-stabilizing maximal independent set algorithms with unreliable communications ⋮ Self-stabilizing distributed algorithm for local mutual inclusion

Cites Work

• Unnamed Item
• Unnamed Item
• A belated proof of self-stabilization
• A self-stabilizing algorithm for maximal matching
• A self-stabilizing distributed algorithm to find the median of a tree graph
• A self-stabilizing algorithm for coloring planar graphs
• Maximal matching stabilizes in quadratic time
• Maximal matching stabilizes in time \(O(m)\)
• A self-stabilizing algorithm for coloring bipartite graphs
• A self-stabilizing distributed algorithm to construct an arbitrary spanning tree of a connected graph
• A SELF-STABILIZING DISTRIBUTED ALGORITHM TO FIND THE CENTER OF A TREE GRAPH
• Self-stabilizing systems in spite of distributed control
• A SELF-STABILIZING DISTRIBUTED ALGORITHM FOR ALL-PAIRS SHORTEST PATH PROBLEM

This page was built for publication: Self-stabilizing algorithms for minimal dominating sets and maximal independent sets