A fast and simple randomized parallel algorithm for maximal matching
From MaRDI portal
Publication:1073573
DOI10.1016/0020-0190(86)90144-4zbMath0588.68036OpenAlexW1964932074MaRDI QIDQ1073573
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)90144-4
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 (33)
Randomized OBDD-based graph algorithms ⋮ An optimal parallel algorithm for maximal matching ⋮ A fast and efficient NC algorithm for maximal matching ⋮ Randomized OBDD-Based Graph Algorithms ⋮ A 2-approximation NC algorithm for connected vertex cover and tree cover ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Improved deterministic distributed matching via rounding ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Node and edge averaged complexities of local graph problems ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Distributed half-integral matching and beyond ⋮ Distributed half-integral matching and beyond ⋮ The maximal f-dependent set problem for planar graphs is in NC ⋮ Fast RNC and NC algorithms for finding a maximal set of paths with an application ⋮ (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Round Compression for Parallel Matching Algorithms ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Parallel complexity of computing a maximal set of disjoint paths ⋮ 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 ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ On the Microscopic View of Time and Messages ⋮ An optimal maximal independent set algorithm for bounded-independence graphs ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Fast RNC and NC algorithms for maximal path sets ⋮ An efficient parallel graph edge matching algorithm and its applications ⋮ Removing randomness in parallel computation without a processor penalty ⋮ Distributed algorithms for matching in hypergraphs
Cites Work
This page was built for publication: A fast and simple randomized parallel algorithm for maximal matching
