A self-stabilizing algorithm for constructing spanning trees

DOI10.1016/0020-0190(91)90111-TzbMath0735.68004OpenAlexW2063615214MaRDI QIDQ1182088

Shing-Tsaan Huang, Hwey-Pyng Yu, Nian-Shing Chen

Publication date: 27 June 1992

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

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90111-t

zbMATH Keywords

distributed systemsfault tolerancespanning treesself-stabilizing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (22)

A self-stabilizing algorithm for strong fairness ⋮ A self-stabilizing algorithm for the st-order problem ⋮ A Stabilizing Algorithm for Finding Two Node-Disjoint Paths in Arbitrary Networks ⋮ Analysis of a memory-efficient self-stabilizing BFS spanning tree construction ⋮ Fault-containing self-stabilizing distributed protocols ⋮ A self-stabilizing algorithm for the maximum flow problem ⋮ Self-stabilizing token circulation in uniform networks ⋮ A self-stabilizing algorithm for constructing breadth-first trees ⋮ SELF-STABILIZING DISTRIBUTED SORTING IN TREE NETWORKS ⋮ Self-stabilizing silent disjunction in an anonymous network ⋮ A self-stabilizing algorithm for maximal matching ⋮ Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks ⋮ The first fully polynomial stabilizing algorithm for BFS tree construction ⋮ Timer-based composition of fault-containing self-stabilizing protocols ⋮ A timestamp based transformation of self-stabilizing programs for distributed computing environments ⋮ A self-stabilizing algorithm for coloring bipartite graphs ⋮ A Framework for Certified Self-Stabilization ⋮ A self-stabilizing graph algorithm: Finding the cutting center of a tree ⋮ A New Polynomial Silent Stabilizing Spanning-Tree Construction Algorithm ⋮ Self-stabilizing depth-first token circulation on networks ⋮ Fault-containing self-stabilization using priority scheduling ⋮ A self-stabilizing distributed algorithm for minimal spanning tree problem in a symmetric graph

Cites Work

• A belated proof of self-stabilization
• An exercise in proving self-stabilization with a variant function
• 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 spanning trees