A fast distributed algorithm for approximating the maximum matching

DOI10.1007/978-3-540-30140-0_24MaRDI QIDQ5464584zbMATH OpenOpenAlexFDO

Authors Edyta Szymańska, Andrzej Czygrinow, Michal Hanckowiak

Publication date 18 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b100428

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25)

Recommendations

• Distributed algorithm for approximating the maximum matching
• Distributed approximate matching
• Distributed approximate matching
• Improved Distributed Approximate Matching
• An efficient distributed algorithm for maximum matching in general graphs

Cited in

(21)

• Distributed algorithm for approximating the maximum matching
• Improved deterministic distributed matching via rounding
• Communication complexity of approximate maximum matching in the message-passing model
• Approximation algorithms for Max Morse matching
• Fast distributed almost stable matchings
• A Local Computation Approximation Scheme to Maximum Matching
• Communication complexity of approximate matching in distributed graphs
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Maintaining bipartite matchings in the presence of failures
• Improved Distributed Approximate Matching
• Fast Distributed Approximations in Planar Graphs
• Distributed approximate matching
• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs
• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• Distributed approximate matching
• Distributed maximum matching verification in CONGEST
• Distributed algorithms for covering, packing and maximum weighted matching
• Distributed approximation for \(f\)-matching
• Distributed algorithms for weighted problems in sparse graphs
• An efficient distributed algorithm for maximum matching in general graphs

This page was built for publication: A fast distributed algorithm for approximating the maximum matching

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