A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2

DOI10.1016/J.TCS.2010.11.032zbMath1263.68175OpenAlexW2050672494MaRDI QIDQ719295

Bernd Hauck, Volker Turau

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.2010.11.032

zbMATH Keywords

approximation algorithmsdistributed algorithmsself-stabilizing algorithmsweighted matching

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 (2)

The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs ⋮ Self-Stabilizing Domination Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stabilization-preserving atomicity refinement
• 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)\)
• Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler
• Distributed Approximate Matching
• Dynamic and self-stabilizing distributed matching
• Paths, Trees, and Flowers
• Distributed Weighted Matching

This page was built for publication: A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2