A parallel search algorithm for directed acyclic graphs

DOI10.1007/BF01937481MaRDI QIDQ795509zbMATH OpenOpenAlexFDO

Authors Ratan K. Ghosh, G. P. Bhattacharjee

Publication date 1984

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01937481

zbMATH Keywords

directed acyclic graphparallel algorithmspanning treeSIMDshared memory modelantilexicographicdepth-first searchingtraversal algorithms

Mathematics Subject Classification ID

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

Recommendations

• Planar Strong Connectivity Helps in Parallel Depth-First Search
• scientific article; zbMATH DE number 4068310
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• scientific article; zbMATH DE number 4065021
• Improved parallel depth-first search in undirected planar graphs

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3635458 (Why is no real title available?)
• scientific article; zbMATH DE number 3635515 (Why is no real title available?)
• Depth-First Search and Linear Graph Algorithms
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Finding Dominators in Directed Graphs
• Gaussian elimination is not optimal
• Merging with parallel processors
• New Parallel-Sorting Schemes
• On the Parallel Evaluation of Polynomials
• Parallel Algorithms in Graph Theory: Planarity Testing
• Parallel Computations in Graph Theory
• Parallel Solution of Recurrence Problems
• The ILLIAC IV Computer

Cited in

(16)

• Parallel algorithms for connectivity problems in graph theory
• Randomized parallel algorithms
• scientific article; zbMATH DE number 6616702 (Why is no real title available?)
• A parallel algorithm for recognizing unordered depth-first search
• A unified approach to parallel depth-first traversals of general trees
• Sequential and parallel solution-biased search for subgraph algorithms
• Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search
• Criterion for a graph to admit a good orientation in terms of leaf blocks
• A random NC algorithm for depth first search
• On computing the number of topological orderings of a directed acyclic graph
• Parallel depth first search. I: Implementation
• Parallel search algorithms for graphs and trees
• A model classifying algorithms as inherently sequential with applications to graph searching
• Prallel algorithms for analyzing activity networks
• Parallel algorithms for a depth first search and a breadth first search
• A note on parallel depth first search

This page was built for publication: A parallel search algorithm for directed acyclic graphs

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