01-10-056
Circuit Bases of Strongly Connected Digraphs
## 01-10-056

#
Abstract:

Circuit Bases of Strongly Connected Digraphs

[PostScript]
[PDF]

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

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.

Presented at the conference *Recent Trends in Graph Theory,
Algebraic Combinatorics, and Graph Algorithms*, Bled (Slovenia)
Sep 24-27 (2001).

**Keywords:**
Strongly conncted digraphs, cycle space, minimum circuit basis

**AMS subject classification:**
05C20 (directed graphs), 05C38 (paths and cycles),
05C85 (graph algorithms)

Return to 2001 working papers list.