A self-stabilizing algorithm for maximal matching

DOI10.1016/0020-0190(92)90015-NzbMath0772.68006OpenAlexW2088809694MaRDI QIDQ1199938

Su-Chu Hsu, Shing-Tsaan Huang

Publication date: 17 January 1993

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

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90015-n

zbMATH Keywords

distributed systemsfault-tolerancemaximal matchingself-stabilizationvariant function

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Related Items (19)

A self-stabilizing algorithm for \(b\)-matching ⋮ An anonymous self-stabilizing algorithm for 1-maximal independent set in trees ⋮ Self-stabilizing algorithms for minimal dominating sets and maximal independent sets ⋮ A self-stabilizing algorithm for the st-order problem ⋮ The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs ⋮ A self-stabilizing algorithm to maximal 2-packing with improved complexity ⋮ Proving convergence of self-stabilizing systems using first-order rewriting and regular languages ⋮ A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs ⋮ Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks ⋮ A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks ⋮ Timer-based composition of fault-containing self-stabilizing protocols ⋮ A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem ⋮ A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2 ⋮ A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph ⋮ A new self-stabilizing maximal matching algorithm ⋮ Self-Stabilizing Domination Algorithms ⋮ Maximal matching stabilizes in time \(O(m)\) ⋮ A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs ⋮ Maximal matching stabilizes in quadratic time

Cites Work

• Probabilistic self-stabilization
• Stabilizing unison
• A belated proof of self-stabilization
• An exercise in proving self-stabilization with a variant function
• A self-stabilizing algorithm for constructing spanning trees
• A self-stabilizing algorithm for constructing breadth-first trees
• Self-stabilizing systems in spite of distributed control
• Unnamed Item
• Unnamed Item

This page was built for publication: A self-stabilizing algorithm for maximal matching