An improved parallel algorithm for maximal matching
From MaRDI portal
Publication:1073571
DOI10.1016/0020-0190(86)90141-9zbMath0588.68035OpenAlexW2073975876MaRDI 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
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)
Related Items (30)
Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs ⋮ Parallel approximation algorithms for maximum weighted matching in general graphs ⋮ An optimal parallel algorithm for maximal matching ⋮ A fast and efficient NC algorithm for maximal matching ⋮ PARALLEL APPROXIMATE MATCHING ⋮ A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH ⋮ Parallel circle-cover algorithms ⋮ o(log4 n) time parallel maximal matching algorithm using linear number of processors ⋮ A parallel algorithm for the maximum 2-chain edge packing problem ⋮ An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm ⋮ Improved deterministic distributed matching via rounding ⋮ Improved distributed degree splitting and edge coloring ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem ⋮ The maximal f-dependent set problem for planar graphs is in NC ⋮ Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality ⋮ Round Compression for Parallel Matching Algorithms ⋮ A randomized NC algorithm for the maximal tree cover 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 on circular-arc graphs ⋮ Unnamed Item ⋮ Distributed Approximate Maximum Matching in the CONGEST Model. ⋮ An efficient parallel graph edge matching algorithm and its applications ⋮ IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH ⋮ Approximating unweighted connectivity problems in parallel ⋮ Removing randomness in parallel computation without a processor penalty ⋮ An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs ⋮ A fast and simple randomized parallel algorithm for maximal matching
This page was built for publication: An improved parallel algorithm for maximal matching
