An improvement on parallel computation of a maximal matching

DOI10.1016/0020-0190(95)00166-2MaRDI QIDQ672837zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 177547 (Why is no real title available?)
• A fast and simple randomized parallel algorithm for maximal matching
• An improved parallel algorithm for maximal matching
• An optimal parallel algorithm for maximal matching
• Removing randomness in parallel computation without a processor penalty

Cited in

(11)

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