Circuit Bases of Strongly Connected Digraphs

Gleiss, Petra M. and Leydold, Josef and Stadler, Peter F. (2001) Circuit Bases of Strongly Connected Digraphs. Preprint Series / Department of Applied Statistics and Data Processing, 40. Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business, Vienna.


Download (283kB)


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. (author's abstract)

Item Type: Paper
Additional Information: published in: Discussiones Mathematicae: Graph Theory 23, pp. 241-260, 2003
Keywords: graph theory / directed graphs / cycle space / relevant circuits / minimum length basis
Classification Codes: MSC 05C20, 05C38, 05C85
Divisions: Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Depositing User: Repository Administrator
Date Deposited: 10 Jul 2006 11:29
Last Modified: 22 Oct 2019 00:41


View Item View Item


Downloads per month over past year

View more statistics