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

Maximal matchingNCParallel algorithmsRNC

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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
• scientific article; zbMATH DE number 1471955

Cites work

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

Cited in

(7)

• A fast and simple randomized parallel algorithm for maximal matching
• 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
• An efficient NC algorithm for approximate maximum weight matching
• Fast RNC and NC algorithms for finding a maximal set of paths with an application
• Distributed algorithms for covering, packing and maximum weighted 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)