Backtrack algorithms for listing certain kinds of subgraphs of a graph are described and analyzed. Included are algorithms for listing all spanning trees, all cycles, all simple cycles, or all of certain other kinds of paths. The algorithms have 0(V plus E) space requirements and 0(V plus E plus EN) time requirements, if the problem graph has V vertices, E edges, and N subgraphs of the type to be listed.
All Science Journal Classification (ASJC) codes
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications