Planar Strong Connectivity Helps in Parallel Depth-First Search

DOI10.1137/S0097539792227077MaRDI QIDQ4326852zbMATH OpenOpenAlexFDO

Authors Ming-Yang Kao

Publication date 27 March 1995

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539792227077

zbMATH Keywords

planar directed graph

Mathematics Subject Classification ID

Graph theory (05C99) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Improved parallel depth-first search in undirected planar graphs
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Planar Depth-First Search in O(\log n) Parallel Time
• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• A linear-processor algorithm for depth-first search in planar graphs

Cited in

(8)

• An optimal parallel algorithm for planar cycle separators
• Depth-first search in directed planar graphs, revisited
• Path-based depth-first search for strong and biconnected components
• Planar Depth-First Search in O(\log n) Parallel Time
• Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
• Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees
• Improved parallel depth-first search in undirected planar graphs
• A parallel search algorithm for directed acyclic graphs

This page was built for publication: Planar Strong Connectivity Helps in Parallel Depth-First Search

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