Parallel Algorithms for Depth-First Searches I. Planar Graphs
From MaRDI portal
Publication:3753502
DOI10.1137/0215058zbMath0612.68059OpenAlexW1998776409MaRDI QIDQ3753502
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215058
depth-first searchplanar undirected graphdepth-first spanning treeinherently sequential problemsunbounded-parallel algorithm
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Improved parallel depth-first search in undirected planar graphs, Fault tolerant depth first search in undirected graphs: simple yet efficient, An optimal parallel algorithm for planar cycle separators, A random NC algorithm for depth first search, On finding optimal and near-optimal lineal spanning trees, A linear-processor algorithm for depth-first search in planar graphs, Subtree isomorphism is NC reducible to bipartite perfect matching, Unnamed Item, A model classifying algorithms as inherently sequential with applications to graph searching, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, Not all planar digraphs have small cycle separators, Parallel search algorithms for graphs and trees, Extending planar graph algorithms to \(K_{3,3}\)-free graphs, Sublinear-time reductions for big data computing, An external-memory depth-first search algorithm for general grid graphs, Via Detours to I/O-Efficient Shortest Paths, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
