An improved parallel algorithm for maximal matching
From MaRDI portal
Publication:1073571
DOI10.1016/0020-0190(86)90141-9zbMath0588.68035MaRDI QIDQ1073571
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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Related Items
Unnamed Item, IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH, PARALLEL APPROXIMATE MATCHING, A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH, o(log4 n) time parallel maximal matching algorithm using linear number of processors, 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, A randomized NC algorithm for the maximal tree cover problem, 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, 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, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs
