Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems

DOI10.1137/110828691zbMath1253.68380OpenAlexW2072015757MaRDI QIDQ3143303

Hiro Ito, Masaki Yamamoto, Yuichi Yoshida

Publication date: 29 November 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110828691

zbMATH Keywords

maximum matchingperfect matchingvertex coverproperty testingset coverconstant-time approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Related Items (6)

Average Sensitivity of Graph Algorithms ⋮ On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions ⋮ Unnamed Item ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Best of two local models: centralized local and distributed local algorithms

This page was built for publication: Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems