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 of 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.
Original language | English (US) |
---|---|
Pages (from-to) | 372-378 |
Number of pages | 7 |
Journal | Communications of the ACM |
Volume | 16 |
Issue number | 6 |
DOIs | |
State | Published - Jun 1 1973 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Computer Science
Keywords
- analysis of algorithms
- graph manipulation
- graphs