A new self-stabilizing maximal matching algorithm
From MaRDI portal
Publication:1008731
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
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