A self-stabilizing algorithm for maximal matching

DOI10.1016/0020-0190(92)90015-NMaRDI QIDQ1199938zbMATH OpenOpenAlexFDO

Authors 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

fault-tolerancedistributed systemsself-stabilizationmaximal matchingvariant function

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Recommendations

• Dynamic and self-stabilizing distributed matching
• Brief Announcement
• A self-stabilizing algorithm for maximal matching in link-register model
• A self-stabilizing algorithm for maximal matching in anonymous networks

Cites work

• scientific article; zbMATH DE number 4035837 (Why is no real title available?)
• scientific article; zbMATH DE number 3446921 (Why is no real title available?)
• A belated proof of self-stabilization
• A self-stabilizing algorithm for constructing breadth-first trees
• A self-stabilizing algorithm for constructing spanning trees
• An exercise in proving self-stabilization with a variant function
• Probabilistic self-stabilization
• Self-stabilizing systems in spite of distributed control
• Stabilizing unison

Cited in

(22)

• Self-Stabilizing Domination Algorithms
• 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
• Dynamic and self-stabilizing distributed matching
• A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Timer-based composition of fault-containing self-stabilizing protocols
• A self-stabilizing algorithm to maximal 2-packing with improved complexity
• 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 self-stabilizing algorithm for the maximum flow problem
• A self-stabilizing algorithm for finding articulation points
• Proving convergence of self-stabilizing systems using first-order rewriting and regular languages
• A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs
• A self-stabilizing algorithm for b-matching
• Maximal matching stabilizes in quadratic time
• Maximal matching stabilizes in time \(O(m)\)
• An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
• Brief Announcement
• A self-stabilizing algorithm for the st-order problem
• A self-stabilizing 23-approximation algorithm for the maximum matching problem
• The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199938)