A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem
From MaRDI portal
Publication:719294
DOI10.1016/j.tcs.2011.05.019zbMath1234.68466OpenAlexW2058465484MaRDI QIDQ719294
Sébastien Tixeuil, Fredrik Manne, Morten Mjelde, Laurence Pilard
Publication date: 10 October 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.019
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed systems (68M14) Approximation algorithms (68W25)
Related Items (4)
The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs ⋮ Conditional matching preclusion for the arrangement graphs ⋮ A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs ⋮ Self-Stabilizing Domination Algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Distance-\(k\) knowledge in self-stabilizing algorithms
- 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
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem