Path-based depth-first search for strong and biconnected components

2000/05/01 by Harold N. Gabow · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Advanced Optical Network Technologies #Algorithm #Biconnected graph #Combinatorics #Computer science #Connectivity #Edge contraction #Graph #Graph power #Interconnection Networks and Systems #Line graph #Mathematics #Strongly connected component #Theoretical computer science #Time complexity

paper · doi:10.1016/s0020-0190(00)00051-x

crossref issued 2000/05/01 · crossref published 2000/05/01 · crossref published-print 2000/05/01 · openalex publication_date 2000/05/01 · crossref created 2002/07/25 · crossref deposited 2019/04/28 · openalex created_date 2025/10/10 · crossref indexed 2026/05/08 · openalex updated_date 2026/07/28

Citations

• Efficient Planarity Testing
• Dividing a Graph into Triconnected Components
• A linear-time algorithm for a special case of disjoint set union
• A transitive closure algorithm
• A strong-connectivity algorithm and its applications in data flow analysis
• Depth-First Search and Linear Graph Algorithms
• A Theorem on Graphs, with an Application to a Problem of Traffic Control

Cited by

• Path-based strong component algorithm [wikipedia]