o(log4 n) time parallel maximal matching algorithm using linear number of processors

DOI10.1080/1063719042000208827zbMath1087.68123OpenAlexW2052634388MaRDI QIDQ4826117

Alak Kumar Datta, Ranjan Kumar Sen

Publication date: 11 November 2004

Published in: Parallel Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/1063719042000208827

zbMATH Keywords

MatchingParallel Random Access MachinesVertex CoverParallel Graph Algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Parallel time and space upper-bounds for the subset-sum problem

Cites Work

• An improved 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
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Parallel Merge Sort
• Parallel Symmetry-Breaking in Sparse Graphs
• A New Parallel Algorithm for the Maximal Independent Set Problem

This page was built for publication: o(log⁴ n) time parallel maximal matching algorithm using linear number of processors