Approximating matchings in parallel
From MaRDI portal
Publication:1261482
DOI10.1016/0020-0190(93)90055-EzbMath0784.68065OpenAlexW1998375300MaRDI QIDQ1261482
Andrew V. Goldberg, Ted Fischer, David J. Haglin, Serge A. Plotkin
Publication date: 16 September 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(93)90055-e
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)
Related Items
Parallel approximation algorithms for maximum weighted matching in general graphs, Distributed algorithm for approximating the maximum matching, Fast primal-dual distributed algorithms for scheduling and matching problems, Approximating weighted matchings in parallel, Matchability and \(k\)-maximal matchings, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- A fast parallel algorithm for routing in permutation networks
- Constructing a Maximal Independent Set in Parallel
- Parallelism in random access machines
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
