Report Number: CS-TR-71-207
Institution: Stanford University, Department of Computer Science
Title: Efficient algorithms for graph manipulation
Author: Hopcroft, John E.
Author: Tarjan, Robert Endre
Date: March 1971
Abstract: 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 is 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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/71/207/CS-TR-71-207.pdf