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

concurrent-read, exclusive-write PRAMdepth-first searchparallel algorithm

Mathematics Subject Classification ID

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

Review text

We present a parallel algorithm for the concurrent-read, exclusive-write PRAM model that determines in \(O(\log^ 2 V)\) time using M(V) processors whether a given directed spanning forest of a given graph corresponds to some unordered depth-first search, where \(M(V)=O(V^{2.376})\) is the number of processors needed to do transitive closure in \(O(\log^ 2 V)\) time. If the answer is ``yes, the depth-first numbering of the vertices is also output. The algorithm can be modified to avoid concurrent reading at the expense of more processors.

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

(9)

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

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)