Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs

DOI10.1007/978-3-642-10631-6_68MaRDI QIDQ3652253zbMATH OpenOpenAlexFDO

Authors Edyta Szymańska, Andrzej Czygrinow, Michal Hanckowiak

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)

Recommendations

• Algorithms – ESA 2004
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
• Distributed algorithm for approximating the maximum matching
• Distributed approximate matching

Cited in

(9)

• An improved constant-time approximation algorithm for maximum~matchings
• Distributed algorithms for random graphs
• An estimator for matching size in low arboricity graphs with two applications
• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Structural results on matching estimation with applications to streaming
• Distributed approximation for \(f\)-matching
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Distributed Approximation Algorithms for the Minimum Dominating Set in K_h-Minor-Free Graphs

This page was built for publication: Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs

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