A fast and efficient NC algorithm for maximal matching

DOI10.1016/0020-0190(95)00106-MzbMath0875.68692OpenAlexW1970561610MaRDI QIDQ1352118

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

Parallel algorithmsNCMaximal matchingRNC

Mathematics Subject Classification ID

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

Related Items (5)

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 ⋮ Fast RNC and NC algorithms for maximal path sets ⋮ An efficient parallel graph edge matching algorithm and its applications

Cites Work

• Unnamed Item
• An improved parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for maximal matching
• An optimal parallel algorithm for maximal matching
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast parallel algorithm for the maximal independent set problem
• Parallel Symmetry-Breaking in Sparse Graphs

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