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)

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

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)