Circuit Bases of Strongly Connected Digraphs

Petra M. Gleiss, Josef Leydold, Peter F. Stadler

Publication: Working/Discussion PaperWU Working Paper

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. (author's abstract)
Original languageEnglish
Place of PublicationVienna
PublisherDepartment of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business
Publication statusPublished - 2001

Publication series

NamePreprint Series / Department of Applied Statistics and Data Processing
No.40

WU Working Paper Series

  • Preprint Series / Department of Applied Statistics and Data Processing

Cite this