A self-stabilizing 23-approximation algorithm for the maximum matching problem

DOI10.1016/J.TCS.2011.05.019MaRDI QIDQ719294zbMATH OpenOpenAlexFDO

Authors Fredrik Manne, Morten Mjelde, Laurence Pilard, Sébastien Tixeuil

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

\(\frac23\)-approximationmaximum matchingself-stabilizing algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• A self-stabilizing algorithm for maximal matching
• scientific article; zbMATH DE number 1735731
• An improved approximation lower bound for finding almost stable maximum matchings
• Polynomial self-stabilizing maximum matching algorithm with approximation ratio 2/3
• A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2
• A self-stabilizing algorithm for b-matching

Cites work

• A self-stabilizing algorithm for maximal matching
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
• Distance-\(k\) knowledge in self-stabilizing algorithms
• scientific article; zbMATH DE number 1863300 (Why is no real title available?)
• Maximal matching stabilizes in quadratic time
• Maximal matching stabilizes in time \(O(m)\)
• Self-stabilization
• Self-stabilizing systems in spite of distributed control

Cited in

(13)

• Stabilizing maximum matching in bipartite networks
• A self-stabilizing algorithm for b-matching
• The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs
• Polynomial self-stabilizing maximum matching algorithm with approximation ratio 2/3
• Self-Stabilizing Domination Algorithms
• scientific article; zbMATH DE number 1735731 (Why is no real title available?)
• A O(m) self-stabilizing algorithm for maximal triangle partition of general graphs
• Dynamic and self-stabilizing distributed matching
• Brief Announcement
• Conditional matching preclusion for the arrangement graphs
• Distributed backup placement in one round and its applications to maximum matching approximation and self-stabilization
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
• A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2

This page was built for publication: A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q719294)