(1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
From MaRDI portal
Publication:6202220
DOI10.1145/3583668.3594570arXiv2212.14425MaRDI QIDQ6202220
Publication date: 26 March 2024
Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2212.14425
Cites Work
- Unnamed Item
- Approximating weighted matchings in parallel
- A simple approximation algorithm for the weighted matching problem
- A fast and simple randomized parallel algorithm for maximal matching
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Linear programming in the semi-streaming model with application to the maximum matching problem
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- On the Distributed Complexity of Computing Maximal Matchings
- Connectivity oracles for failure prone graphs
- Distributed Minimum Cut Approximation
- Improved Distributed Approximate Matching
- Local Computation
- Linear-Time Approximation for Maximum Weight Matching
- Distributed Approximate Matching
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Sublinear-Time Parallel Algorithms for Matching and Related Problems
- Faster scaling algorithms for general graph matching problems
- Distributed Verification and Hardness of Distributed Approximation
- Distributed Approximate Maximum Matching in the CONGEST Model.
- Weighted Matchings via Unweighted Augmentations
- Deterministic distributed edge-coloring with fewer colors
- Distributed Approximation of Maximum Independent Set and Maximum Matching
- Distributed Weighted Matching
- Maximum matching and a polyhedron with 0,1-vertices
