Planar Depth-First Search in O(\log n) Parallel Time

DOI10.1137/0219047MaRDI QIDQ3474884zbMATH OpenOpenAlexFDO

Authors Torben Hagerup

Publication date 1990

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

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

zbMATH Keywords

depth-first searchparallel computingplanar graphsPriority CRCW PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Recommendations

• Improved parallel depth-first search in undirected planar graphs
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• A linear-processor algorithm for depth-first search in planar graphs
• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• A note on parallel depth first search
• Depth-first search in directed planar graphs, revisited
• Depth-First Search in Directed Planar Graphs, Revisited
• Parallel Depth-First Search in General Directed Graphs
• Parallel algorithms for a depth first search and a breadth first search
• Planar Strong Connectivity Helps in Parallel Depth-First Search

Cited in

(21)

• Depth-first search is inherently sequential
• A random NC algorithm for depth first search
• A linear-processor algorithm for depth-first search in planar graphs
• A parallel algorithm for recognizing unordered depth-first search
• Parallel depth first search. II: Analysis
• Parallel search algorithms for graphs and trees
• Distributed algorithms for depth-first search
• An optimal parallel algorithm for planar cycle separators
• Parallel approximation schemes for problems on planar graphs
• Depth-first search in directed planar graphs, revisited
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• Depth-First Search Using O(n) Bits
• An efficient parallel algorithm for shifting the root of a depth first spanning tree
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• Planar Strong Connectivity Helps in Parallel Depth-First Search
• IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH
• A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH
• Improved parallel depth-first search in undirected planar graphs
• Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search
• Depth-First Search in Directed Planar Graphs, Revisited

This page was built for publication: Planar Depth-First Search in $O(\log n)$ Parallel Time

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