Distributed algorithm for approximating the maximum matching

DOI10.1016/J.DAM.2003.10.004zbMath1064.68067OpenAlexW1983211386MaRDI QIDQ1887042

Andrzej Czygrinow, Michał Hanćkowiak, Edyta Szymańska

Publication date: 23 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2003.10.004

zbMATH Keywords

maximum matchingdistributed algorithm

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) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (5)

Distributed algorithms for weighted problems in sparse graphs ⋮ Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well ⋮ Improved deterministic distributed matching via rounding ⋮ A two-stage hardware scheduler combining greedy and optimal scheduling ⋮ Why locally-fair maximal flows in client-server networks perform well

Cites Work

• Approximating matchings in parallel
• On the Distributed Complexity of Computing Maximal Matchings
• Locality in Distributed Graph Algorithms

This page was built for publication: Distributed algorithm for approximating the maximum matching