A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
From MaRDI portal
Publication:666086
DOI10.1016/J.JPDC.2009.11.006zbMath1233.68179OpenAlexW2034396486MaRDI QIDQ666086
Hamamache Kheddouci, Nabil Guellati
Publication date: 7 March 2012
Published in: Journal of Parallel and Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jpdc.2009.11.006
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)
Related Items (12)
Self-stabilizing algorithm for two disjoint minimal dominating sets ⋮ Self-stabilizing algorithms for minimal global powerful alliance sets in graphs ⋮ Fault tolerant network constructors ⋮ The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs ⋮ Self-stabilizing 2-minimal dominating set algorithms based on loop composition ⋮ Efficient self-stabilizing algorithms for minimal total \(k\)-dominating sets in graphs ⋮ A theorem of Ore and self-stabilizing algorithms for disjoint minimal dominating sets ⋮ A \(4n\)-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon ⋮ Self-Stabilizing Domination Algorithms ⋮ New Self-Stabilizing Algorithms for Minimal Weakly Connected Dominating Sets ⋮ Self-stabilizing distributed algorithm for local mutual inclusion ⋮ A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
- Stabilization-preserving atomicity refinement
- A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem
- A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems
- Empire of colonies: Self-stabilizing and self-organizing distributed algorithm
- A new self-stabilizing maximal matching algorithm
- Linear time self-stabilizing colorings
- Self-stabilizing coloration in anonymous planar networks
- A self-stabilizing algorithm for maximal matching
- Self-stabilization of dynamic systems assuming only read/write atomicity
- 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
- Fault-containing self-stabilizing distributed protocols
- 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
- A self-stabilizing algorithm for finding a minimal 2-dominating set assuming the distributed demon model
- On the complexity of distributed graph coloring with local minimality constraints
- A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET
- Locality in Distributed Graph Algorithms
- Self-stabilizing systems in spite of distributed control
- Resource Bounds for Self-Stabilizing Message-Driven Protocols
- Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
- Dynamic and self-stabilizing distributed matching
- Distributed Computing - IWDC 2003
- High Performance Computing - HiPC 2003
- A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph
- What cannot be computed locally!
- Principles of Distributed Systems
This page was built for publication: A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
