Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs

DOI10.1016/j.ipl.2009.03.022zbMath1211.68278OpenAlexW2009748163MaRDI QIDQ989486

Subhas Kumar Ghosh, Atish Datta Chowdhury, Satyajit Banerjee

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.03.022

zbMATH Keywords

maximum matchinggraph algorithmsapproximation algorithmsdistributed algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• On the Distributed Complexity of Computing Maximal Matchings
• A linear-time approximation algorithm for weighted matchings in graphs
• The price of being near-sighted
• Efficient Distributed Weighted Matchings on Trees
• Deterministic coin tossing with applications to optimal parallel list ranking
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Weighted Matching

This page was built for publication: Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs