Distributed approximate maximum matching in the CONGEST model
DOI10.4230/LIPICS.DISC.2018.6zbMATH Open1497.68558OpenAlexW2896802580MaRDI QIDQ5090895FDOQ5090895
Authors: Mohamad Ahmadi, Fabian Kuhn, Rotem Oshman 
Publication date: 21 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9795/pdf/LIPIcs-DISC-2018-6.pdf/
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15) Communication complexity, information complexity (68Q11)
Cites Work
- Paths, Trees, and Flowers
- Distributed Computing: A Locality-Sensitive Approach
- Distributed verification and hardness of distributed approximation
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- An improved parallel algorithm for maximal matching
- An information statistics approach to data stream and communication complexity
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Local computation: lower and upper bounds
- An improved constant-time approximation algorithm for maximum~matchings
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Title not available (Why is that?)
- The price of being near-sighted
- Distributed approximate matching
- Distributed Weighted Matching
- Distributed Algorithm for Better Approximation of the Maximum Matching
- Distributed approximation of maximum independent set and maximum matching
- Title not available (Why is that?)
- A faster distributed algorithm for computing maximal matchings deterministically
- Improved deterministic distributed matching via rounding
- Title not available (Why is that?)
Cited In (20)
- Fast Distributed Approximation for Max-Cut
- Communication complexity of approximate maximum matching in the message-passing model
- Minimum cost flow in the CONGEST model
- Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
- Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
- Distributed approximation for \(f\)-matching
- (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 approximation of maximum independent set and maximum matching
- Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
- Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
- Linear-in-\(\varDelta \) lower bounds in the LOCAL model
- Distributed approximate matching
- Improved deterministic distributed matching via rounding
- Node and edge averaged complexities of local graph problems
- Distributed dense subgraph detection and low outdegree orientation
- Distributed maximum matching verification in CONGEST
- The Match-Maker: Constant-Space Distributed Majority via Random Walks
- Distributed approximate matching
This page was built for publication: Distributed approximate maximum matching in the CONGEST model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090895)
