A parallel algorithm for recognizing unordered depth-first search

DOI10.1016/0020-0190(88)90172-XzbMATH Open0658.68083OpenAlexW2093602721MaRDI QIDQ1111396FDOQ1111396

Jeffrey Scott Vitter, Catherine A. Schevon

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)

Cites Work

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

Cited In (6)

• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• Title not available (Why is that?)
• Depth-first search is inherently sequential
• Title not available (Why is that?)
• An efficient parallel algorithm for shifting the root of a depth first spanning tree
• A note on parallel depth first search

   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 👍 👎

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)