SIAM Journal on Computing · 1973 · 841 citations · 4 references
ComputingComputer ScienceAlgorithmsGraph AlgorithmsGraph AnalyticsGraph TheoryGraph Construction AlgorithmsGraph DecompositionsGraph Partitioning ApproximationGraph ProcessingGraph-based Partitioning
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.
4
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations