Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs

DOI10.1007/978-3-642-10631-6_68zbMath1272.05193OpenAlexW1579008745MaRDI QIDQ3652253

Edyta Szymańska, Michał Hanćkowiak, Andrzej Czygrinow

Publication date: 17 December 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-10631-6_68

zbMATH Keywords

maximum matching problemdeterministic distributed approximation algorithmgraphs of bounded arboricity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (5)

Distributed algorithms for random graphs ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Structural results on matching estimation with applications to streaming ⋮ Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs ⋮ An estimator for matching size in low arboricity graphs with two applications

This page was built for publication: Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs