Parallel search algorithms for graphs and trees
From MaRDI portal
Publication:1204800
DOI10.1016/0020-0255(93)90088-4zbMath0764.68050MaRDI 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 graphs; parallel algorithms; shortest paths; depth-first search; directed acyclic graphs; breadth-first search; forests; spanning trees; decomposition search; parallel random access machine; tree traversal
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W15: Distributed algorithms
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
