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