A fast and efficient NC algorithm for maximal matching

DOI10.1016/0020-0190(95)00106-MMaRDI QIDQ1352118zbMATH OpenOpenAlexFDO

Authors Zhi-Zhong Chen

Publication date 27 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)00106-m

zbMATH Keywords

NCParallel algorithmsMaximal matchingRNC

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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) Distributed algorithms (68W15)

Recommendations

• An optimal parallel algorithm for maximal matching
• An improvement on parallel computation of a maximal matching
• A fast and simple randomized parallel algorithm for maximal matching
• An improved parallel algorithm for maximal matching
• Publication:4489037

Cites work

• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for maximal matching
• A fast parallel algorithm for the maximal independent set problem
• An improved parallel algorithm for maximal matching
• An optimal parallel algorithm for maximal matching
• Parallel Symmetry-Breaking in Sparse Graphs

Cited in

(7)

• Fast RNC and NC algorithms for maximal path sets
• An efficient parallel graph edge matching algorithm and its applications
• A 2-approximation NC algorithm for connected vertex cover and tree cover
• Fast RNC and NC algorithms for finding a maximal set of paths with an application
• Distributed algorithms for covering, packing and maximum weighted matching
• A fast and simple randomized parallel algorithm for maximal matching
• An efficient NC algorithm for approximate maximum weight matching

This page was built for publication: A fast and efficient NC algorithm for maximal matching

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