A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem

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

zbMATH Keywords

maximum matching; self-stabilizing algorithm; \(\frac23\)-approximation

Mathematics Subject Classification ID

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