1973/09/01 by John E. Hopcroft, Robert E. Tarjan · 6 citations
Computer Science · Mathematics · #Interconnection Networks and Systems #Algorithms and Data Compression #Parallel Computing and Optimization Techniques #Graph #Computer science #Combinatorics #Constant (computer programming) #Mathematics #Theoretical computer science #Algorithm
paper · doi:10.1137/0202012
openalex publication_date 1973/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02
An algorithm for dividing a graph into triconnected components is presented. When implemented on a random access computer, the algorithm requires O(V + E) time and space to analyze a graph with V vertices and E edges. The algorithm is both theoretically optimal to within a constant factor and efficient in practice.