Accession Number : AD0726169

Title :   Efficient Algorithms for Graph Manipulation,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Hopcroft,John ; Tarjan,Robert

Report Date : MAR 1971

Pagination or Media Count : 23

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. (Author)

Descriptors :   (*GRAPHICS, ALGORITHMS), COMPUTER PROGRAMS, EXPERIMENTAL DATA, ITERATIONS, EFFICIENCY

Subject Categories : Theoretical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE