Distributed approximate maximum matching in the CONGEST model

DOI10.4230/LIPICS.DISC.2018.6MaRDI QIDQ5090895zbMATH OpenOpenAlexFDO

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/

zbMATH Keywords

communication complexitymaximum matchingdistributed graph algorithmsdeterministic rounding

Mathematics Subject Classification ID

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)

Recommendations

• Improved Distributed Approximate Matching
• Improved deterministic distributed matching via rounding
• Improved deterministic distributed matching via rounding
• Distributed approximation of maximum independent set and maximum matching
• Distributed approximate matching

Cites work

• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• scientific article; zbMATH DE number 2079379 (Why is no real title available?)
• scientific article; zbMATH DE number 3399279 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A faster distributed algorithm for computing maximal matchings deterministically
• An improved constant-time approximation algorithm for maximum~matchings
• 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
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Weighted Matching
• Distributed approximate matching
• Distributed approximation of maximum independent set and maximum matching
• Distributed verification and hardness of distributed approximation
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Improved deterministic distributed matching via rounding
• Local computation: lower and upper bounds
• Paths, Trees, and Flowers
• The price of being near-sighted

Cited in

(21)

• 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
• Linear-in- lower bounds in the LOCAL model
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Distributed approximate matching
• Linear-in-\(\Delta\) lower bounds in the LOCAL model
• 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)