Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs
DOI10.1137/19M1279241zbMath1445.05098arXiv1807.07645MaRDI QIDQ5115699
Publication date: 18 August 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1807.07645
Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Hypergraphs (05C65) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (2)
Cites Work
- Unnamed Item
- Approximating weighted matchings in parallel
- A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
- Improved deterministic distributed matching via rounding
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- Distributed Algorithm for Better Approximation of the Maximum Matching
- Improved Distributed Approximate Matching
- The Locality of Distributed Symmetry Breaking
- Decomposition of Graphs Into Closed and Endless Chains
- Distributed Approximate Matching
- The price of being near-sighted
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- An Improved Distributed Algorithm for Maximal Independent Set
- Distributed Degree Splitting, Edge Coloring, and Orientations
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
- Distributed Approximate Maximum Matching in the CONGEST Model.
- Some simple distributed algorithms for sparse networks
- Deterministic distributed edge-coloring with fewer colors
- Distributed Approximation of Maximum Independent Set and Maximum Matching
- Concentration and Moment Inequalities for Polynomials of Independent Random Variables
This page was built for publication: Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs