
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