Distributed Approximate Maximum Matching in the CONGEST Model.
From MaRDI portal
Publication:5090895
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/
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.