Open AccessEnumeration of the Elementary Circuits of a Directed Graph
Author(s) -
Robert E. Tarjan
Publication year - 1973
Publication title -
siam journal on computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.533
H-Index - 122
eISSN - 1095-7111
pISSN - 0097-5397
DOI - 10.1137/0202017
Subject(s) - enumeration , backtracking , graph , combinatorics , electronic circuit , mathematics , directed graph , discrete mathematics , graph theory , algorithm , computer science , physics , quantum mechanics
An algorithm to enumerate all the elementary circuits of a directed graph is presented. The algorithm uses back-tracking with lookahead to avoid unnecessary work, and it has a time bound of $O ((V+E)(C+1))$ when applied to a graph with $V$ vertices, $E$ edges, and $C$ elementary circuits. Keywords: Algorithm, circuit, cycle, graph
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