A self-stabilizing 23-approximation algorithm for the maximum matching problem
DOI10.1016/J.TCS.2011.05.019zbMATH Open1234.68466OpenAlexW2058465484MaRDI QIDQ719294FDOQ719294
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
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
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)
Cites Work
- Self-stabilization
- Self-stabilizing systems in spite of distributed control
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Distance-\(k\) knowledge in self-stabilizing algorithms
- A self-stabilizing algorithm for maximal matching
- An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
- Title not available (Why is that?)
- Maximal matching stabilizes in quadratic time
- Maximal matching stabilizes in time \(O(m)\)
Cited In (13)
- 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
- Title not available (Why is that?)
- A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2
- A \(O(m)\) self-stabilizing algorithm for maximal triangle partition of general graphs
- Stabilizing maximum matching in bipartite networks
- 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
- Self-Stabilizing Domination Algorithms
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)
