A random NC algorithm for depth first search
From MaRDI portal
We present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithms is an RNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on a P-RAM. The run time of the algorithm is \(O(T_{MM}(n)\log^ 3 n)\), and the number of processors used is \(P_{MM}(n)\) where \(T_{MM}n)\) and \(P_{MM}(n)\) are the time and number of processors needed to find a minimum weight perfect matching on an n vertex graph with maximum edge weight n.
Recommendations
- Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- Parallel Depth-First Search in General Directed Graphs
- Planar Depth-First Search in O(\log n) Parallel Time
- A parallel algorithm for recognizing unordered depth-first search
Cites work
- A fast parallel algorithm for the maximal independent set problem
- A parallel algorithm for the maximal path problem
- A parallel search algorithm for directed acyclic graphs
- A Separator Theorem for Planar Graphs
- A taxonomy of problems with fast parallel algorithms
- Constructing a perfect matching is in random NC
- Depth-First Search and Linear Graph Algorithms
- Depth-first search is inherently sequential
- scientific article; zbMATH DE number 3635515 (Why is no real title available?)
- Matching is as easy as matrix inversion
- Network Flow and Testing Graph Connectivity
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- Parallel Computations in Graph Theory
Cited in
(24)- A parallel algorithm for recognizing unordered depth-first search
- A parallel algorithm for the maximum 2-chain edge packing problem
- An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm
- Parallel complexity of computing a maximal set of disjoint paths
- A model classifying algorithms as inherently sequential with applications to graph searching
- Not all planar digraphs have small cycle separators
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- A remark on maximum matching of line graphs
- An optimal parallel algorithm for planar cycle separators
- Designing checkers for programs that run in parallel
- On the performance of the depth first search algorithm in supercritical random graphs
- Frameworks for designing in-place graph algorithms
- A 2-approximation NC algorithm for connected vertex cover and tree cover
- Depth-First Search Using O(n) Bits
- Parallel Depth-First Search in General Directed Graphs
- Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph
- The recognition problem of graph search trees
- A framework for in-place graph algorithms
- Improved parallel depth-first search in undirected planar graphs
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Extending planar graph algorithms to \(K_{3,3}\)-free graphs
- Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
- Parallel complexity of depth-first-search and maximal path in restricted graph classes
- A complexity theory of efficient parallel algorithms
This page was built for publication: A random NC algorithm for depth first search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104756)