A Local Computation Approximation Scheme to Maximum Matching

Abstract

We present a polylogarithmic local computation matching algorithm which guarantees a $(1-\eps)$-approximation to the maximum matching in graphs of bounded degree.

Appears in Approx 2013

References in corpus (1)

• Fast Local Computation Algorithms

Cited by in corpus (5)

• A Local Algorithm for Constructing Spanners in Minor-Free Graphs
• A Local Algorithm for the Sparse Spanning Graph Problem
• Non-Local Probes Do Not Help with Graph Problems
• Local Computation Algorithms for Graphs of Non-Constant Degrees
• Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs