A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem
From MaRDI portal
Publication:719294
DOI10.1016/j.tcs.2011.05.019zbMath1234.68466MaRDI 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
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68M14: Distributed systems
68W25: Approximation algorithms
Related Items
Conditional matching preclusion for the arrangement graphs, A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs, The first polynomial self-stabilizing 1-maximal matching algorithm for general 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