An optimal parallel algorithm for maximal matching
From MaRDI portal
Publication:1341686
DOI10.1016/0020-0190(94)90130-9zbMath0823.68040MaRDI QIDQ1341686
Publication date: 9 January 1995
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)90130-9
Related Items
On efficient implicit OBDD-based algorithms for maximal matchings, Distributed algorithms for covering, packing and maximum weighted matching, A simple randomized parallel algorithm for maximal f-matchings, An improvement on parallel computation of a maximal matching, An efficient parallel graph edge matching algorithm and its applications, A fast and efficient NC algorithm for maximal matching, An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs, A 2-approximation NC algorithm for connected vertex cover and tree cover
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved parallel algorithm for maximal matching
- A fast and simple randomized parallel algorithm for maximal matching
- Deterministic coin tossing with applications to optimal parallel list ranking
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Constructing a Maximal Independent Set in Parallel