Parallel Algorithms for Depth-First Searches I. Planar Graphs

DOI10.1137/0215058zbMATH Open0612.68059OpenAlexW1998776409MaRDI QIDQ3753502FDOQ3753502

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

Recommendations

Improved parallel depth-first search in undirected planar graphs
Planar Depth-First Search in $O(\log n)$ Parallel Time
Parallel algorithms for a depth first search and a breadth first search
Parallel Depth-First Search in General Directed Graphs
A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
Efficient parallel algorithms for planar $st$-graphs
scientific article
Optimal parallel algorithms on planar graphs
Parallel breadth-first search algorithms for trees and graphs
Efficient parallel algorithms for shortest paths in planar graphs

depth-first search planar undirected graph depth-first spanning tree inherently sequential problems unbounded-parallel algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10)

Cited In (38)

A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
Randomized parallel algorithms
An external-memory depth-first search algorithm for general grid graphs
Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees
Planar Strong Connectivity Helps in Parallel Depth-First Search
A parallel algorithm for recognizing unordered depth-first search
Efficient parallel algorithms for breadth first spanning forests of general graphs
Extending planar graph algorithms to $K_{3,3}$-free graphs
An optimal parallel algorithm for planar cycle separators
Depth-first search is inherently sequential
A random NC algorithm for depth first search
Fault tolerant depth first search in undirected graphs: simple yet efficient
A linear-processor algorithm for depth-first search in planar graphs
On finding optimal and near-optimal lineal spanning trees
Improved parallel depth-first search in undirected planar graphs
Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search
Parallel depth first search. I: Implementation
Parallel search algorithms for graphs and trees
Sublinear-time reductions for big data computing
A new distributed depth-first-search algorithm
Via Detours to I/O-Efficient Shortest Paths
An efficient parallel algorithm for shifting the root of a depth first spanning tree
A model classifying algorithms as inherently sequential with applications to graph searching
Parallel algorithms for a depth first search and a breadth first search
An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm
Parallel depth first search. II: Analysis
Not all planar digraphs have small cycle separators
Subtree isomorphism is NC reducible to bipartite perfect matching
Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier
A parallel search algorithm for directed acyclic graphs
Title not available (Why is that?)
Title not available (Why is that?)
A note on parallel depth first search
A parallel algorithm for the maximal path problem
Planar Depth-First Search in $O(\log n)$ Parallel Time
Depth-First Search in Directed Planar Graphs, Revisited

This page was built for publication: Parallel Algorithms for Depth-First Searches I. Planar Graphs

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