Accession Number:

AD0726169

Title:

Efficient Algorithms for Graph Manipulation,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

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

Subject Categories:

  • Theoretical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE