An improved constant-time approximation algorithm for maximum~matchings

DOI10.1145/1536414.1536447zbMath1304.05112OpenAlexW1539682630MaRDI QIDQ5172716

Hiro Ito, Yuichi Yoshida, Masaki Yamamoto

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536447

zbMATH Keywords

maximum matchingproperty testingminimum vertex coverminimum set coverconstant-time approximation algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (15)

Can we locally compute sparse connected subgraphs? ⋮ Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Approximately Counting Triangles in Sublinear Time ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Constructing near spanning trees with few local inspections ⋮ Sublinear-time Algorithms ⋮ Sublinear Graph Approximation Algorithms ⋮ Local algorithms for sparse spanning graphs ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ An Efficient Partitioning Oracle for Bounded-Treewidth Graphs ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ⋮ Distributed Approximate Maximum Matching in the CONGEST Model. ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: An improved constant-time approximation algorithm for maximum~matchings