Algorithm 447: efficient algorithms for graph manipulation
John E. Hopcroft, Robert Endre Tarjan · Communications of the ACM · 1973
Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths of iterative and each iteration produces a new path between two vertices already on paths. (The start vertex can be specified dynamically.) If V is the number of vertices and E is the number of edges, each algorithm requires time and space proportional to max ( V, E ) when executed on a random access computer.
Cited by 985 works. doi:10.1145/362248.362272 Open-access PDF
Authors
References
- Graph theory
- GRAPH THEORY
- An algorithm for the blocks and cutnodes of a graph
- Planarity testing in V log V steps: extended abstract
- Computer Recognition and Extraction of Planar Graphs from the Incidence Matrix
- On the Time Required to Detect Cycles and Connectivity in Directed Graphs
- Implementation and analysis of efficient graph planarity testing algorithms