Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
From MaRDI portal
Publication:1317488
DOI10.1016/0022-0000(93)90042-UzbMath0795.68086OpenAlexW4242757385MaRDI QIDQ1317488
Ming-Yang Kao, Philip N. Klein
Publication date: 18 September 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(93)90042-u
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Related Items
An optimal parallel algorithm for planar cycle separators, Depth-first search in directed planar graphs, revisited, Size-estimation framework with applications to transitive closure and reachability, Topologically trivial closed walks in directed surface graphs, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved algorithms for graph four-connectivity
- Deterministic parallel list ranking
- Depth-first search is inherently sequential
- Finding small simple cycle separators for 2-connected planar graphs
- Parallel ear decomposition search (EDS) and st-numbering in graphs
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- A random NC algorithm for depth first search
- An efficient parallel algorithm for planarity
- Parallel concepts in graph theory
- Fast and efficient solution of path algebra problems
- Faster optimal parallel prefix sums and list ranking
- Parallel Depth-First Search in General Directed Graphs
- An Efficient Parallel Biconnectivity Algorithm
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
- Parallel algorithms for planar graph isomorphism and related problems
- Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
- A Separator Theorem for Planar Graphs
- Parallel Prefix Computation
- An O(logn) parallel connectivity algorithm
- Parallel Transitive Closure and Point Location in Planar Structures
- Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
- Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees
- A simple parallel tree contraction algorithm
- Depth-First Search and Linear Graph Algorithms
