An improved constant-time approximation algorithm for maximum~matchings

DOI10.1145/1536414.1536447MaRDI QIDQ5172716zbMATH OpenOpenAlexFDO

Authors Yuichi Yoshida, Masaki Yamamoto, Hiro Ito

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

property testingmaximum matchingminimum vertex coverminimum set coverconstant-time approximation algorithms

Mathematics Subject Classification ID

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

Recommendations

• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Sublinear graph approximation algorithms
• Improved Distributed Approximate Matching
• On constant time approximation of parameters of bounded degree graphs
• Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs

Cited in

(30)

• Constructing near spanning trees with few local inspections
• An efficient partitioning oracle for bounded-treewidth graphs
• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Sublinear-time Algorithms
• Approximately counting triangles in sublinear time
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Space-efficient local computation algorithms
• An Improved Approximation Algorithm for the Matching Augmentation Problem
• An improvement on Łuczak's connected matchings method
• Approximation algorithms for Max Morse matching
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Exponentially faster massively parallel maximal matching
• Borel oracles. An analytical approach to constant-time algorithms
• Approximating the distance to monotonicity of Boolean functions
• Sublinear time estimation of degree distribution moments: the arboricity connection
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Locally computing edge orientations
• Sublinear algorithms for TSP via path covers
• Sublinear time approximation of the cost of a metric k-nearest neighbor graph
• Can we locally compute sparse connected subgraphs?
• Sublinear graph approximation algorithms
• Sublinear time algorithms and complexity of approximate maximum matching
• On approximating the number of k-cliques in sublinear time
• scientific article; zbMATH DE number 1003276 (Why is no real title available?)
• Faster algorithm for finding maximum 1-restricted simple 2-matchings
• Local algorithms for sparse spanning graphs
• Distributed maximum matching verification in CONGEST
• Additive noise mechanisms for making randomized approximation algorithms differentially private
• Distributed approximate maximum matching in the CONGEST model
• On constant time approximation of parameters of bounded degree graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5172716)