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

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

zbMATH Keywords

maximum matchingself-stabilizing algorithm\(\frac23\)-approximation

Mathematics Subject Classification ID

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