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