Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68W15: Distributed algorithms

Related Items

Size-estimation framework with applications to transitive closure and reachability, An optimal parallel algorithm for planar cycle separators

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