A Local Computation Approximation Scheme to Maximum Matching

DOI10.1007/978-3-642-40328-6_19zbMath1405.68448arXiv1306.5003OpenAlexW1641959094MaRDI QIDQ2851862

Shai Vardi, Yishay Mansour

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.5003

zbMATH Keywords

maximum matchingapproximation algorithmssublinear algorithmslocal computation algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (10)

New techniques and tighter bounds for local computation algorithms ⋮ Can we locally compute sparse connected subgraphs? ⋮ Average Sensitivity of Graph Algorithms ⋮ Unnamed Item ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Constant-time local computation algorithms ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Unnamed Item ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ Local algorithms for sparse spanning graphs

This page was built for publication: A Local Computation Approximation Scheme to Maximum Matching