Parallel Depth-First Search in General Directed Graphs

DOI10.1137/0219025zbMath0692.68053OpenAlexW2020283440MaRDI QIDQ3034839

Alok Aggarwal, Richard J. Anderson, Ming-Yang Kao

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219025

zbMATH Keywords

parallel algorithmsdirected graphsrandomized NC algorithmdepth- first searchcycle separator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15) Graph theory (05C99)

Related Items (17)

A linear time algorithm for finding depth-first spanning trees on trapezoid graphs ⋮ Improved parallel depth-first search in undirected planar graphs ⋮ Fault tolerant depth first search in undirected graphs: simple yet efficient ⋮ An optimal parallel algorithm for planar cycle separators ⋮ Depth-first search in directed planar graphs, revisited ⋮ Size-estimation framework with applications to transitive closure and reachability ⋮ A randomized NC algorithm for the maximal tree cover problem ⋮ Parallel complexity of computing a maximal set of disjoint paths ⋮ A model classifying algorithms as inherently sequential with applications to graph searching ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Not all planar digraphs have small cycle separators ⋮ Parallel search algorithms for graphs and trees ⋮ Unnamed Item ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

This page was built for publication: Parallel Depth-First Search in General Directed Graphs