Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs

DOI10.1137/19M1279241zbMath1445.05098arXiv1807.07645MaRDI QIDQ5115699

David G. Harris

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

zbMATH Keywords

hypergraphmatchingedge coloringderandomizationLOCALNash-Williams decomposition

Mathematics Subject Classification ID

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)

On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Distributed coloring of hypergraphs

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