2001-04.pmg-ley-pfs
Circuit Bases of Strongly Connected Digraphs
Abstract
The cycle space of a strongly connected graph has a basis consisting
of directed circuits. The concept of relevant circuits is introduced
as a generalization of the relevant cycles in undirected graphs. A
polynomial time algorithm for the computation of a minimum weight
directed circuit basis is outlined.
Mathematics Subject Classification:
05C20 (directed graphs), 05C38 (paths and cycles), 05C85 (graph algorithms)
Keywords:
graph theory, directed graphs, cycle space, relevant circuits, minimum length basis
Download Preprint
Josef.Leydold@statistik.wu-wien.ac.at