A Local Computation Approximation Scheme to Maximum Matching

2013/06/20 by Mansour, Yishay, Vardi, Shai · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1306.5003

Abstract

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

Cited by

• A Fast Coloring Oracle for Average Case Hypergraphs

Related

• Local Computation Algorithms for Maximum Matching: New Lower Bounds
• Local Computation Algorithms for Graphs of Non-Constant Degrees
• New Deterministic Approximation Algorithms for Fully Dynamic Matching
• A framework for boosting matching approximation: parallel, distributed, and dynamic
• On the Approximation Performance of Degree Heuristics for Matching