Parallel search algorithms for graphs and trees
DOI10.1016/0020-0255(93)90088-4zbMath0764.68050OpenAlexW1991996594MaRDI QIDQ1204800
Publication date: 29 March 1993
Published in: Information Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0255(93)90088-4
planar graphsparallel algorithmsshortest pathsdepth-first searchdirected acyclic graphsbreadth-first searchforestsspanning treesdecomposition searchparallel random access machinetree traversal
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parallel strong orientation of an undirected graph
- A parallel search algorithm for directed acyclic graphs
- Improved algorithms for graph four-connectivity
- Depth-first search is inherently sequential
- An optimal parallel processor bound in strong orientation of an undirected graph
- On efficient parallel strong orientation
- Finding small simple cycle separators for 2-connected planar graphs
- Parallel ear decomposition search (EDS) and st-numbering in graphs
- An improved parallel algorithm that computes the BFS numbering of a directed graph
- A new graph triconnectivity algorithm and its parallelization
- Faster optimal parallel prefix sums and list ranking
- Parallel Depth-First Search in General Directed Graphs
- Applications of Path Compression on Balanced Trees
- Parallel breadth-first search algorithms for trees and graphs
- Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
- Planar Depth-First Search in $O(\log n)$ Parallel Time
- An Efficient Parallel Biconnectivity Algorithm
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- Parallel Merge Sort
- A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
- Parallel algorithms for planar graph isomorphism and related problems
- Parallel algorithms for a depth first search and a breadth first search
- Parallel algorithms for connectivity problems in graph theory
- Finding Dominators in Directed Graphs
- Parallel Computations in Graph Theory
- Fast parallel sorting algorithms
- Implementation of simultaneous memory address access in models that forbid it
- Dividing a Graph into Triconnected Components
- Depth-First Search and Linear Graph Algorithms
