An improvement on parallel computation of a maximal matching

DOI10.1016/0020-0190(95)00166-2zbMATH Open0875.68464OpenAlexW1987734035MaRDI QIDQ672837FDOQ672837

Authors: Yijie Han 

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00166-2

Recommendations

• An optimal parallel algorithm for maximal matching
• An improved parallel algorithm for maximal matching
• o(log⁴ n) time parallel maximal matching algorithm using linear number of processors
• Publication:4489037

zbMATH Keywords

Parallel algorithmsGraph algorithmsMaximal matchingOptimal algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cites Work

• An improved parallel algorithm for maximal matching
• An optimal parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for maximal matching
• Removing randomness in parallel computation without a processor penalty
• Title not available (Why is that?)

Cited In (11)

• Efficient parallel algorithms for parameterized problems
• A fast and efficient NC algorithm for maximal matching
• An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
• An efficient parallel graph edge matching algorithm and its applications
• An improved parallel algorithm for maximal matching
• A Local Computation Approximation Scheme to Maximum Matching
• Improved processor bounds for combinatorial problems in RNC
• An optimal parallel algorithm for maximal matching
• A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem
• o(log⁴ n) time parallel maximal matching algorithm using linear number of processors
• A fast and simple randomized parallel algorithm for maximal matching

This page was built for publication: An improvement on parallel computation of a maximal matching

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