Approximating matchings in parallel

DOI10.1016/0020-0190(93)90055-EMaRDI QIDQ1261482zbMATH OpenOpenAlexFDO

Authors Ted Fischer, Andrew V. Goldberg, David J. Haglin, Serge 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

zbMATH Keywords

parallel computationapproximately maximum matchingNick's class

Mathematics Subject Classification ID

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)

Recommendations

• Parallel approximation algorithms for maximum weighted matching in general graphs
• Approximating weighted matchings in parallel
• scientific article; zbMATH DE number 1759463
• An improved parallel algorithm for maximal matching
• An optimal parallel algorithm for maximal matching

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• A fast parallel algorithm for routing in permutation networks
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Constructing a Maximal Independent Set in Parallel
• Constructing a perfect matching is in random NC
• Matching is as easy as matrix inversion
• Parallelism in random access machines

Cited in

(22)

• A Local Computation Approximation Scheme to Maximum Matching
• Parallel computation of matchings in trees
• PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
• Processor efficient parallel matching
• On parallel complexity of maximum \(f\)-matching and the degree sequence problem
• Round compression for parallel matching algorithms
• Towards more precise parallel biconnectivity approximation
• scientific article; zbMATH DE number 1759463 (Why is no real title available?)
• Almost fully-parallel parentheses matching
• Improved processor bounds for combinatorial problems in RNC
• Approximation algorithms for maximum matchings in undirected graphs
• Linear time approximation algorithms for~degree~constrained subgraph problems
• Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
• scientific article; zbMATH DE number 1003267 (Why is no real title available?)
• Distributed algorithm for approximating the maximum matching
• Distributed maximum matching verification in CONGEST
• scientific article; zbMATH DE number 549852 (Why is no real title available?)
• Matchability and \(k\)-maximal matchings
• Parallel approximation algorithms for maximum weighted matching in general graphs
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Finding maximum matching for bipartite graphs in parallel
• Approximating weighted matchings in parallel

This page was built for publication: Approximating matchings in parallel

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