Distributed Approximate Maximum Matching in the CONGEST Model.

DOI10.4230/LIPIcs.DISC.2018.6zbMath1497.68558OpenAlexW2896802580MaRDI QIDQ5090895

Mohamad Ahmadi, Rotem Oshman, Fabian Kuhn

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9795/pdf/LIPIcs-DISC-2018-6.pdf/

zbMATH Keywords

maximum matchingcommunication complexitydistributed graph algorithmsdeterministic rounding

Mathematics Subject Classification ID

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

Related Items (7)

Node and edge averaged complexities of local graph problems ⋮ Minimum cost flow in the CONGEST model ⋮ (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model ⋮ Optimal Message-Passing with Noisy Beeps ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An information statistics approach to data stream and communication complexity
• An improved parallel algorithm for maximal matching
• A faster distributed algorithm for computing maximal matchings deterministically
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Local Computation
• Distributed Approximate Matching
• The price of being near-sighted
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Distributed Computing: A Locality-Sensitive Approach
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Distributed Verification and Hardness of Distributed Approximation
• An improved constant-time approximation algorithm for maximum~matchings
• Paths, Trees, and Flowers
• Distributed Approximation of Maximum Independent Set and Maximum Matching
• Distributed Weighted Matching
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Distributed Approximate Maximum Matching in the CONGEST Model.