A new self-stabilizing maximal matching algorithm

DOI10.1016/j.tcs.2008.12.022zbMath1163.68372arXivcs/0701189OpenAlexW2110600065MaRDI QIDQ1008731

Fredrik Manne, Laurence Pilard, Morten Mjelde, Sébastien Tixeuil

Publication date: 30 March 2009

Published in: Theoretical Computer Science, Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0701189

zbMATH Keywords

maximal matchingself-stabilizing algorithmsmaximal matchin problemself stabilzing algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items

A self-stabilizing algorithm for \(b\)-matching ⋮ The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs ⋮ A framework for automated distributed implementation of component-based models ⋮ Self-stabilizing Cuts in Synchronous Networks ⋮ A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs ⋮ A self-stabilizing algorithm for cut problems in synchronous networks ⋮ A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks ⋮ 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 new self-stabilizing maximal matching algorithm ⋮ Self-Stabilizing Domination Algorithms ⋮ Parameterized synthesis of self-stabilizing protocols in symmetric networks ⋮ Parameterized Synthesis of Self-Stabilizing Protocols in Symmetric Rings ⋮ A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs

Cites Work

• An efficient self-stabilizing distance-2 coloring algorithm
• A new self-stabilizing maximal matching algorithm
• A self-stabilizing algorithm for maximal 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
• Self-stabilizing systems in spite of distributed control
• Dynamic and self-stabilizing distributed matching
• Unnamed Item
• Unnamed Item
• Unnamed Item