Depth-first search is inherently sequential

DOI10.1016/0020-0190(85)90024-9zbMath0572.68051OpenAlexW2085467310WikidataQ55923944 ScholiaQ55923944MaRDI QIDQ1062456

Publication date: 1985

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(85)90024-9

zbMATH Keywords

parallel computation polynomial time complete rooted graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Automated Verification of Parallel Nested DFS, On efficient parallel strong orientation, On parallelizing a greedy heuristic for finding small dominant sets, The incremental maintenance of a depth-first-search tree in directed acyclic graphs, A theory of strict P-completeness, A multi-threading algorithm to detect and remove cycles in vertex- and arc-weighted digraph, Distributed algorithms for depth-first search, Model Checking of Biological Systems, Improved parallel depth-first search in undirected planar graphs, On the parallel computation of the biconnected and strongly connected co-components of graphs, A parallel algorithm for the maximal path problem, Connected components in $O(\log^{3/2}n)$ parallel time for the CREW PRAM, An optimal parallel algorithm for planar cycle separators, Fast parallel graph searching with applications, A random NC algorithm for depth first search, A topological approach to dynamic graph connectivity, The multi-tree approach to reliability in distributed networks, Depth-first search in directed planar graphs, revisited, A variable neighborhood search for the network design problem with relays, A parallel algorithm for the maximum 2-chain edge packing problem, Incremental algorithm for maintaining a DFS tree for undirected graphs, Depth-First Search Using $$O(n)$$ Bits, On Dynamic DFS Tree in Directed Graphs, Graph representation of the fixed route dial-a-ride problem, DFS tree construction: Algorithms and characterizations, A complexity theory of efficient parallel algorithms, A P-complete graph partition problem, Digital Bifurcation Analysis of Internet Congestion Control Protocols, An 0(log n) parallel algorithm for strong connectivity augmentation problem, Parallel algorithms on interval graphs, $\Delta{} ^ p_ 2$-complete lexicographically first maximal subgraph problems, Symbolic coloured SCC decomposition, Efficient parallel algorithms for path problems in directed graphs, 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, Parallel search algorithms for graphs and trees, Dynamical modeling and analysis of large cellular regulatory networks, The lexicographically first topological order problem is NLOG-complete, Unnamed Item, Unnamed Item, Sublinear-time reductions for big data computing, Concurrent disjoint set union, A theory of strict P-completeness, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier, The lexicographically first maximal subgraph problems:P-completeness andNC algorithms, The Recognition Problem of Graph Search Trees, Some remarks on distributed depth-first search., Sublinear-time reductions for big data computing, A Stack-Slicing Algorithm for Multi-Core Model Checking, A linear-time certifying algorithm for recognizing generalized series-parallel graphs, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, THE TRANSITIVE CLOSURE AND RELATED ALGORITHMS OF DIGRAPH ON THE RECONFIGURABLE ARCHITECTURE

Cites Work