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

R. C. Read, R. E. Tarjan

Research output: Contribution to journalArticle

154 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 languageEnglish (US)
Pages (from-to)237-252
Number of pages16
JournalNetworks
Volume5
Issue number3
DOIs
StatePublished - Jan 1 1975

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'BOUNDS ON BACKTRACK ALGORITHMS FOR LISTING CYCLES, PATHS, AND SPANNING TREES.'. Together they form a unique fingerprint.

  • Cite this