Parallel complexity of computing a maximal set of disjoint paths

DOI10.1016/0020-0190(92)90044-VzbMath0742.68029OpenAlexW2050624731MaRDI QIDQ1186594

Alok Aggarwal

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90044-v

zbMATH Keywords

parallel complexitydepth-first searchNCPRAMsmaximal path problempolylogarithmic time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• A fast and simple randomized parallel algorithm for maximal matching
• A random NC algorithm for depth first search
• Parallel Depth-First Search in General Directed Graphs
• An efficient parallel algorithm for shifting the root of a depth first spanning tree

This page was built for publication: Parallel complexity of computing a maximal set of disjoint paths