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

DOI10.1016/J.IPL.2009.03.022MaRDI QIDQ989486zbMATH OpenOpenAlexFDO

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

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

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)