An improved parallel algorithm for maximal matching

DOI10.1016/0020-0190(86)90141-9MaRDI QIDQ1073571zbMATH OpenOpenAlexFDO

Authors Amos Israeli, Yossi Shiloach

Publication date 1986

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(86)90141-9

zbMATH Keywords

CRCW-PRAMparallel computation

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

A parallel \(O(\log^ 3| E|)\) algorithm for finding a maximal matching in a graph G(V,E) is presented. The model of computation is the CRCW-PRAM, and \(| V| +| E|\) processors are used. This algorithm is a substantial improvement upon the two previous algorithms known to us. These algorithms by \textit{R. M. Karp} and \textit{W. Wigderson} [Proc. 16th Ann. ACM Symp. Theory of Computing, 266-272 (1984)] and \textit{G. Lev} [Size bounds and parallel algorithms for networks, Tech. Rep. CST-8-80, Dept. Comput. Sci., Univ. Edinburgh (1980)] achieve \(O(\log^ 4| E|)\) depth with \(| E|^ 3/\log | E|\) and \(| E| +| V|\) processors respectively. The last one though having a better performance than the first, only applies to bipartite graphs.

Recommendations

• An optimal parallel algorithm for maximal matching
• An efficient parallel graph edge matching algorithm and its applications
• A fast and simple randomized parallel algorithm for maximal matching
• An improvement on parallel computation of a maximal matching
• scientific article; zbMATH DE number 1471955

Cited in

(44)

• An adjustable linear time parallel algorithm for maximum weight bipartite matching
• A fast and simple randomized parallel algorithm for maximal matching
• Parallel circle-cover algorithms
• A parallel algorithm for the maximum 2-chain edge packing problem
• An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm
• A randomized NC algorithm for the maximal tree cover problem
• Approximating matchings in parallel
• An efficient parallel graph edge matching algorithm and its applications
• Removing randomness in parallel computation without a processor penalty
• An optimal parallel algorithm for maximal matching
• Finding maximum matching for bipartite graphs in parallel
• A fast and efficient NC algorithm for maximal matching
• An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
• Approximating unweighted connectivity problems in parallel
• Improved deterministic distributed matching via rounding
• Improved distributed degree splitting and edge coloring
• Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs
• Parallel approximation algorithms for maximum weighted matching in general graphs
• On the parameterized parallel complexity and the vertex cover problem
• scientific article; zbMATH DE number 4215388 (Why is no real title available?)
• A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem
• scientific article; zbMATH DE number 4160789 (Why is no real title available?)
• Efficient algorithms for finding maximum matching in graphs
• The Maximum Partition Matching Problem with Applications
• PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
• IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH
• scientific article; zbMATH DE number 1471955 (Why is no real title available?)
• scientific article; zbMATH DE number 1759463 (Why is no real title available?)
• PARALLEL APPROXIMATE MATCHING
• A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH
• o(log⁴ n) time parallel maximal matching algorithm using linear number of processors
• Distributed approximate maximum matching in the CONGEST model
• Round compression for parallel matching algorithms
• scientific article; zbMATH DE number 975369 (Why is no real title available?)
• Graph search algorithms and maximum bipartite matching algorithm on the hypercube network model
• Parallel algorithms on circular-arc graphs
• The maximal f-dependent set problem for planar graphs is in NC
• Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality
• On the parallel complexity of the alternating Hamiltonian cycle problem
• Using maximal independent sets to solve problems in parallel
• A simple randomized parallel algorithm for maximal f-matchings
• An improvement on parallel computation of a maximal matching
• The maximal \(f\)-dependent set problem for planar graphs is in NC
• Parallel algorithms for bipartite matching problems on distributed memory computers

This page was built for publication: An improved parallel algorithm for maximal matching

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