A parallel algorithm for recognizing unordered depth-first search

DOI10.1016/0020-0190(88)90172-XMaRDI QIDQ1111396zbMATH OpenOpenAlexFDO

Authors Catherine A. Schevon, Jeffrey Scott Vitter

Publication date 1988

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

Full work available at URL https://doi.org/10.1016/0020-0190(88)90172-x

zbMATH Keywords

parallel algorithmdepth-first searchconcurrent-read, exclusive-write PRAM

Mathematics Subject Classification ID

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

Recommendations

• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Planar Depth-First Search in $O(\log n)$ Parallel Time
• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• A random NC algorithm for depth first search
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications

Cites work

• A parallel search algorithm for directed acyclic graphs
• A random NC algorithm for depth first search
• Finding the maximum, merging, and sorting in a parallel computation model

Cited in

(7)

• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• scientific article; zbMATH DE number 861625 (Why is no real title available?)
• Depth-first search is inherently sequential
• A random NC algorithm for depth first search
• scientific article; zbMATH DE number 865205 (Why is no real title available?)
• An efficient parallel algorithm for shifting the root of a depth first spanning tree
• A note on parallel depth first search

This page was built for publication: A parallel algorithm for recognizing unordered depth-first search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111396)