Approximating matchings in parallel
A matching in an undirected graph \(G=(V,E)\) is a set \(M\subseteq E\) of edges such that no two edges of \(M\) share a vertex. The matching problem is to find a matching of maximum cardinality. This problem is not known to be in NC (solvable in polylog time using a polynomial number of processors) even for bipartite graphs except in certain special cases; the best results to date are sublinear-time algorithms [\textit{A. V. Goldberg}, \textit{S. A. Plotkin} and \textit{P. M. Vaidya}, J. Algorithms 14, No. 2, 180-213 (1993; Zbl 0769.68034)] and probabilistic algorithms [\textit{R. M. Karp}, \textit{E. Upful} and \textit{A. Wigderson}, Combinatorica 6, 35- 48 (1986; Zbl 0646.05051)]. The paper under review presents another compromise: can approximate algorithm which, for fixed \(k>0\), finds a matching with cardinality at last \(k/(k+1)\) times the maximum in \(O(k^ 4\log^ 3n)\) time using \(O(k_ n^{2k+2})\) processors on an \(n\)-vertex graph; with \(k\) constant this shows that approximating a maximum matching to within a constant factor is in NC. The model of parallel computation used is the exclusive-read, exclusive-write parallel random-access machine.
- 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
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- Matching is as easy as matrix inversion
- Parallelism in random access machines
- Parallel computation of matchings in trees
- Improved processor bounds for combinatorial problems in RNC
- Finding maximum matching for bipartite graphs in parallel
- Almost fully-parallel parentheses matching
- Distributed algorithm for approximating the maximum matching
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Processor efficient parallel matching
- A Local Computation Approximation Scheme to Maximum Matching
- Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
- Parallel approximation algorithms for maximum weighted matching in general graphs
- Linear time approximation algorithms for~degree~constrained subgraph problems
- scientific article; zbMATH DE number 1003267 (Why is no real title available?)
- scientific article; zbMATH DE number 1303038 (Why is no real title available?)
- PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
- scientific article; zbMATH DE number 549852 (Why is no real title available?)
- scientific article; zbMATH DE number 1759463 (Why is no real title available?)
- On parallel complexity of maximum \(f\)-matching and the degree sequence problem
- Round compression for parallel matching algorithms
- Matchability and \(k\)-maximal matchings
- Towards more precise parallel biconnectivity approximation
- Distributed maximum matching verification in CONGEST
- Approximation algorithms for maximum matchings in undirected graphs
- 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)
