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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom