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

DOI10.1007/978-3-642-10631-6_68zbMATH Open1272.05193OpenAlexW1579008745MaRDI QIDQ3652253FDOQ3652253

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

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

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)

Cited In (9)

• An improved constant-time approximation algorithm for maximum~matchings
• Distributed algorithms for random graphs
• Title not available (Why is that?)
• An estimator for matching size in low arboricity graphs with two applications
• 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)