Finding strong components using depth-first search
From MaRDI portal
Publication:6563999
DOI10.1016/j.ejc.2023.103815zbMATH Open1542.05171MaRDI QIDQ6563999
Robert Endre Tarjan, Uri Zwick
Publication date: 28 June 2024
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Path-based depth-first search for strong and biconnected components
- A space-efficient algorithm for finding strongly connected components
- A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
- A linear-time algorithm for a special case of disjoint set union
- A strong-connectivity algorithm and its applications in data flow analysis
- I/O- and CPU-optimal recognition of strongly connected components
- On computing the transitive closure of a relation
- On finding the strongly connected components in a directed graph
- A \(0(| V | \cdot | E |)\) algorithm for maximum matching of graphs
- Algorithms for dense graphs and networks on the random access computer
- Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
- Efficient determination of the transitive closure of a directed graph
- Space-Efficient Implementations of Graph Search Methods
- Graph Algorithms
- Approximating Transitive Reductions for Directed Networks
- Efficient Planarity Testing
- Efficiency of a Good But Not Linear Set Union Algorithm
- An Implementation of Tarjan's Algorithm for the Block Triangularization of a Matrix
- Dividing a Graph into Triconnected Components
- Approximating the Minimum Equivalent Digraph
- Union-Find with Constant Time Deletions
- Sequential and Parallel Algorithms and Data Structures
- Paths, Trees, and Flowers
- A transitive closure algorithm
- The Transitive Reduction of a Directed Graph
- Depth-First Search and Linear Graph Algorithms
- Transitive compaction in parallel via branchings
- Mathematical recreations
This page was built for publication: Finding strong components using depth-first search
