A parallel search algorithm for directed acyclic graphs

DOI10.1007/BF01937481zbMath0542.68049OpenAlexW1978615272MaRDI QIDQ795509

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 graphspanning treeparallel algorithmSIMDshared memory modelantilexicographicdepth-first searchingtraversal algorithms

Mathematics Subject Classification ID

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

Related Items

Prallel algorithms for analyzing activity networks ⋮ Criterion for a graph to admit a good orientation in terms of leaf blocks ⋮ A random NC algorithm for depth first search ⋮ A parallel algorithm for recognizing unordered depth-first search ⋮ Parallel algorithms for connectivity problems in graph theory ⋮ A unified approach to parallel depth-first traversals of general trees ⋮ A model classifying algorithms as inherently sequential with applications to graph searching ⋮ Parallel search algorithms for graphs and trees ⋮ Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search ⋮ A note on parallel depth first search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gaussian elimination is not optimal
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Parallel Algorithms in Graph Theory: Planarity Testing
• Finding Dominators in Directed Graphs
• Parallel Solution of Recurrence Problems
• Merging with parallel processors
• Parallel Computations in Graph Theory
• New Parallel-Sorting Schemes
• The ILLIAC IV Computer
• Depth-First Search and Linear Graph Algorithms
• On the Parallel Evaluation of Polynomials

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