A random NC algorithm for depth first search
From MaRDI portal
Publication:1104756
DOI10.1007/BF02122548zbMath0647.68060OpenAlexW2049327803WikidataQ56114900 ScholiaQ56114900MaRDI QIDQ1104756
Publication date: 1988
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02122548
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items
Improved parallel depth-first search in undirected planar graphs, An optimal parallel algorithm for planar cycle separators, A 2-approximation NC algorithm for connected vertex cover and tree cover, A parallel algorithm for recognizing unordered depth-first search, Designing checkers for programs that run in parallel, A remark on maximum matching of line graphs, A parallel algorithm for the maximum 2-chain edge packing problem, An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm, Depth-First Search Using $$O(n)$$ Bits, A complexity theory of efficient parallel algorithms, Parallel complexity of computing a maximal set of disjoint paths, A model classifying algorithms as inherently sequential with applications to graph searching, Frameworks for designing in-place graph algorithms, A Framework for In-place Graph Algorithms, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, Not all planar digraphs have small cycle separators, Extending planar graph algorithms to \(K_{3,3}\)-free graphs, Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier, The Recognition Problem of Graph Search Trees, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
Cites Work
- A parallel search algorithm for directed acyclic graphs
- Depth-first search is inherently sequential
- Matching is as easy as matrix inversion
- A parallel algorithm for the maximal path problem
- Constructing a perfect matching is in random NC
- A taxonomy of problems with fast parallel algorithms
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- A fast parallel algorithm for the maximal independent set problem
- A Separator Theorem for Planar Graphs
- Network Flow and Testing Graph Connectivity
- Parallel Computations in Graph Theory
- Depth-First Search and Linear Graph Algorithms
- Unnamed Item
