An optimal parallel algorithm for planar cycle separators
From MaRDI portal
Publication:1900892
DOI10.1007/BF01192047zbMath0830.68057OpenAlexW2047198574WikidataQ57761204 ScholiaQ57761204MaRDI QIDQ1900892
Kentaro Toyama, Ming-Yang Kao, Shang-Hua Teng
Publication date: 25 October 1995
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01192047
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal parallel algorithms on planar graphs
- Finding Euler tours in parallel
- Deterministic parallel list ranking
- Depth-first search is inherently sequential
- Finding small simple cycle separators for 2-connected planar graphs
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- A random NC algorithm for depth first search
- A linear-processor algorithm for depth-first search in planar graphs
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
- Faster optimal parallel prefix sums and list ranking
- Parallel Depth-First Search in General Directed Graphs
- Efficient parallel algorithms for series parallel graphs
- Planar Depth-First Search in $O(\log n)$ Parallel Time
- 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
- Parallel Prefix Computation
- Parallel Tree Contraction Part 2: Further Applications
- Planar Strong Connectivity Helps in Parallel Depth-First Search
- A simple parallel tree contraction algorithm
- Depth-First Search and Linear Graph Algorithms
