Distributed Algorithm for Better Approximation of the Maximum Matching

DOI10.1007/3-540-45071-8_26MaRDI QIDQ3082932zbMATH OpenOpenAlexFDO

Authors Andrzej Czygrinow, Michal Hanckowiak

Publication date 18 March 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-45071-8_26

zbMATH Keywords

algorithmmaximum matchings

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Recommendations

• Distributed algorithm for approximating the maximum matching
• Algorithms – ESA 2004
• An efficient distributed algorithm for maximum matching in general graphs
• Distributed near-optimal matching
• Distributed near-optimal matching
• On the distributed complexity of computing maximal matchings
• scientific article; zbMATH DE number 1303560
• Distributed approximation of maximum independent set and maximum matching
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs

Cited in

(12)

• Distributed algorithm for extrema-finding in circular configuration of processors
• Distributed algorithm for approximating the maximum matching
• Improved deterministic distributed matching via rounding
• Improved Distributed Approximate Matching
• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• Distributed approximate maximum matching in the CONGEST model
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• The Match-Maker: Constant-Space Distributed Majority via Random Walks
• Distributed maximum matching verification in CONGEST
• Distributed approximation for \(f\)-matching
• On the distributed complexity of the semi-matching problem
• Distributed algorithms for weighted problems in sparse graphs

This page was built for publication: Distributed Algorithm for Better Approximation of the Maximum Matching

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