Improved parallel depth-first search in undirected planar graphs

DOI10.1007/3-540-57155-8_266MaRDI QIDQ5060132zbMATH OpenOpenAlexFDO

Authors Kentaro Toyama, Ming-Yang Kao, Shang-Hua Teng

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• An optimal parallel algorithm for planar cycle separators
• A linear-processor algorithm for depth-first search in planar graphs
• Planar Strong Connectivity Helps in Parallel Depth-First Search
• Planar Depth-First Search in O(\log n) Parallel Time

Cites work

• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• A random NC algorithm for depth first search
• A simple parallel tree contraction algorithm
• An optimal linked list prefix algorithm on a local memory computer
• Depth-First Search and Linear Graph Algorithms
• Depth-first search is inherently sequential
• Deterministic parallel list ranking
• Efficient parallel algorithms for series parallel graphs
• Faster optimal parallel prefix sums and list ranking
• Finding Euler tours in parallel
• Finding small simple cycle separators for 2-connected planar graphs
• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 3902654 (Why is no real title available?)
• scientific article; zbMATH DE number 4064466 (Why is no real title available?)
• scientific article; zbMATH DE number 4064511 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3422404 (Why is no real title available?)
• Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
• Optimal parallel algorithms on planar graphs
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Parallel algorithms for planar graph isomorphism and related problems
• Parallel Depth-First Search in General Directed Graphs
• Parallel Prefix Computation
• Planar Depth-First Search in O(\log n) Parallel Time
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

Cited in

(12)

• A linear-processor algorithm for depth-first search in planar graphs
• An optimal parallel algorithm for planar cycle separators
• Depth-first search in directed planar graphs, revisited
• Parallel Depth-First Search in General Directed Graphs
• Planar Depth-First Search in O(\log n) Parallel Time
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• scientific article; zbMATH DE number 4064511 (Why is no real title available?)
• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• Planar Strong Connectivity Helps in Parallel Depth-First Search
• Depth-First Search in Directed Planar Graphs, Revisited
• Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs
• A parallel search algorithm for directed acyclic graphs

This page was built for publication: Improved parallel depth-first search in undirected planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5060132)