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

DOI10.1016/J.IPL.2009.03.022zbMATH Open1211.68278OpenAlexW2009748163MaRDI QIDQ989486FDOQ989486

Authors: Satyajit Banerjee, Atish Datta Chowdhury, Subhas Kumar Ghosh 

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

approximation algorithmsdistributed algorithmsgraph algorithmsmaximum matching

Mathematics Subject Classification ID

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

Cites Work

• Distributed Computing: A Locality-Sensitive Approach
• 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
• Deterministic coin tossing with applications to optimal parallel list ranking
• Distributed Weighted Matching
• Efficient Distributed Weighted Matchings on Trees

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

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