BOUNDS ON BACKTRACK ALGORITHMS FOR LISTING CYCLES, PATHS, AND SPANNING TREES.

R. C. Read; R. E. Tarjan

doi:10.1002/net.1975.5.3.237

BOUNDS ON BACKTRACK ALGORITHMS FOR LISTING CYCLES, PATHS, AND SPANNING TREES.

R. C. Read, R. E. Tarjan

Research output: Contribution to journal › Article › peer-review

183 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	237-252
Number of pages	16
Journal	Networks
Volume	5
Issue number	3
DOIs	https://doi.org/10.1002/net.1975.5.3.237
State	Published - 1975

All Science Journal Classification (ASJC) codes

Software
Information Systems
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1002/net.1975.5.3.237

Cite this

@article{0d4085a9139c4cc692e4d6065b435bee,

title = "BOUNDS ON BACKTRACK ALGORITHMS FOR LISTING CYCLES, PATHS, AND SPANNING TREES.",

abstract = "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.",

author = "Read, {R. C.} and Tarjan, {R. E.}",

year = "1975",

doi = "10.1002/net.1975.5.3.237",

language = "English (US)",

volume = "5",

pages = "237--252",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - BOUNDS ON BACKTRACK ALGORITHMS FOR LISTING CYCLES, PATHS, AND SPANNING TREES.

AU - Read, R. C.

AU - Tarjan, R. E.

PY - 1975

Y1 - 1975

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0016523213&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0016523213&partnerID=8YFLogxK

U2 - 10.1002/net.1975.5.3.237

DO - 10.1002/net.1975.5.3.237

M3 - Article

AN - SCOPUS:0016523213

SN - 0028-3045

VL - 5

SP - 237

EP - 252

JO - Networks

JF - Networks

IS - 3

ER -

BOUNDS ON BACKTRACK ALGORITHMS FOR LISTING CYCLES, PATHS, AND SPANNING TREES.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this