Improved parallel depth-first search in undirected planar graphs
From MaRDI portal
Publication:5060132
DOI10.1007/3-540-57155-8_266zbMath1504.68170OpenAlexW2097855961MaRDI QIDQ5060132
Kentaro Toyama, Shang-Hua Teng, Ming-Yang Kao
Publication date: 18 January 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-57155-8_266
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- 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
- A simple parallel tree contraction algorithm
- An optimal linked list prefix algorithm on a local memory computer
- Depth-First Search and Linear Graph Algorithms
