A parallel algorithm for the maximal path problem

DOI10.1007/BF02579320zbMath0641.68105MaRDI QIDQ1100916

Richard J. Anderson

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmundirected graphmaximal pathdepth first search tree

Mathematics Subject Classification ID

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

Related Items

A random NC algorithm for depth first search

Cites Work

• Depth-first search is inherently sequential
• Matching is as easy as matrix inversion
• Parallelism and the maximal path problem
• Constructing a perfect matching is in random NC
• A taxonomy of problems with fast parallel algorithms
• A fast parallel algorithm for the maximal independent set problem
• Parallelism in random access machines