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

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

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1863300 (Why is no real title available?)
• 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
• 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)

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

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)