Premium
Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
Author(s) -
Read R. C.,
Tarjan R. E.
Publication year - 1975
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.1975.5.3.237
Subject(s) - spanning tree , listing (finance) , algorithm , computer science , combinatorics , graph , minimum spanning tree , mathematics , finance , economics
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+E) space requirements and 0(V+E+EN) time requirements, if the problem graph has V vertices, E edges, and N subgraphs of the type to be listed.