Accession Number:

AD0726169

Title:

Efficient Algorithms for Graph Manipulation,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Hopcroft,John
• Tarjan,Robert

Report Date:

1971-03-01

Pagination or Media Count:

23.0

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 maxV,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