A self-stabilizing algorithm for constructing breadth-first trees
From MaRDI portal
Publication:1186586
DOI10.1016/0020-0190(92)90264-VzbMath0743.68065OpenAlexW2085991314MaRDI QIDQ1186586
Nian-Shing Chen, Shing-Tsaan Huang
Publication date: 28 June 1992
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(92)90264-v
Network design and communication in computer systems (68M10) Parallel algorithms in computer science (68W10) Data structures (68P05)
Related Items (30)
Competitive self-stabilizing \(k\)-clustering ⋮ An improved self-stabilizing algorithm for biconnectivity and bridge-connectivity ⋮ A self-stabilizing distributed algorithm to construct an arbitrary spanning tree of a connected graph ⋮ A self-stabilizing algorithm for the st-order problem ⋮ Self-stabilizing 2-minimal dominating set algorithms based on loop composition ⋮ An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs ⋮ Analysis of a memory-efficient self-stabilizing BFS spanning tree construction ⋮ An efficient fault-containing self-stabilizing algorithm for the shortest path problem ⋮ A self-stabilizing algorithm for the maximum flow problem ⋮ Maximum metric spanning tree made Byzantine tolerant ⋮ Self-stabilizing silent disjunction in an anonymous network ⋮ A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET ⋮ A self-stabilizing algorithm for maximal matching ⋮ Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks ⋮ A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity ⋮ How to improve snap-stabilizing point-to-point communication space complexity? ⋮ The first fully polynomial stabilizing algorithm for BFS tree construction ⋮ A self-stabilizing algorithm for constructing weakly connected minimal dominating sets ⋮ Snap-Stabilizing Waves in Anonymous Networks ⋮ Request-based token passing for self-stabilizing mutual exclusion ⋮ Short correctness proofs for two self-stabilizing algorithms under the distributed daemon model ⋮ A self-stabilizing algorithm for detecting fundamental cycles in a graph ⋮ A self-stabilizing graph algorithm: Finding the cutting center of a tree ⋮ Optimized silent self-stabilizing scheme for tree-based constructions ⋮ A New Polynomial Silent Stabilizing Spanning-Tree Construction Algorithm ⋮ A SELF-STABILIZING ALGORITHM FOR FINDING ARTICULATION POINTS ⋮ Self-stabilizing depth-first token circulation on networks ⋮ A self-stabilizing distributed algorithm for minimal spanning tree problem in a symmetric graph ⋮ A self-stabilizing algorithm for the shortest path problem in a distributed system ⋮ A self-stabilizing algorithm for the shortest path problem assuming the distributed demon
Cites Work
- A belated proof of self-stabilization
- An exercise in proving self-stabilization with a variant function
- A self-stabilizing algorithm for constructing spanning trees
- Self-stabilization (in spite of distributed control) in tree-structured systems
- Self-stabilizing systems in spite of distributed control
- Token systems that self-stabilize
This page was built for publication: A self-stabilizing algorithm for constructing breadth-first trees
