Parallel Depth-First Search in General Directed Graphs

DOI10.1137/0219025MaRDI QIDQ3034839zbMATH OpenOpenAlexFDO

Authors 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

directed graphsparallel algorithmsrandomized NC algorithmdepth- first searchcycle separator

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4064511
• A random NC algorithm for depth first search
• Improved parallel depth-first search in undirected planar graphs
• An optimal parallel algorithm for planar cycle separators
• A linear-processor algorithm for depth-first search in planar graphs

Cited in

(27)

• Size-estimation framework with applications to transitive closure and reachability
• Scalable Parallel DFPN Search
• Improved parallel depth-first search in undirected planar graphs
• Parallel algorithms for a depth first search and a breadth first search
• A framework for in-place graph algorithms
• Relational depth-first-search with applications
• Depth-First Search in Directed Planar Graphs, Revisited
• Bipartite perfect matching is in quasi-NC
• Depth-first search in directed planar graphs, revisited
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• Not all planar digraphs have small cycle separators
• A randomized NC algorithm for the maximal tree cover problem
• scientific article; zbMATH DE number 7561709 (Why is no real title available?)
• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• Parallel complexity of computing a maximal set of disjoint paths
• A model classifying algorithms as inherently sequential with applications to graph searching
• scientific article; zbMATH DE number 4064511 (Why is no real title available?)
• scientific article; zbMATH DE number 865205 (Why is no real title available?)
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Planar Depth-First Search in $O(\log n)$ Parallel Time
• An optimal parallel algorithm for planar cycle separators
• Frameworks for designing in-place graph algorithms
• A random NC algorithm for depth first search
• A unified approach to parallel depth-first traversals of general trees
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Parallel search algorithms for graphs and trees
• Fault tolerant depth first search in undirected graphs: simple yet efficient

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

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