Circuit Bases of Strongly Connected Digraphs

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

doi:10.57938/8d53d6da-88c5-4bed-8985-24c77bfe021f

Circuit Bases of Strongly Connected Digraphs

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

Institute for Statistics and Mathematics

Publication: Working/Discussion Paper › WU Working Paper

53 Downloads (Pure)

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 language	English
Place of Publication	Vienna
Publisher	Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business
DOIs	https://doi.org/10.57938/8d53d6da-88c5-4bed-8985-24c77bfe021f
Publication status	Published - 2001

Publication series

Series	Preprint Series / Department of Applied Statistics and Data Processing
Number	40

WU Working Paper Series

Preprint Series / Department of Applied Statistics and Data Processing

Access to Document

10.57938/8d53d6da-88c5-4bed-8985-24c77bfe021fLicence: Unspecified

DocumentFinal published version, 277 KBLicence: Unspecified

Check availability

University Library Catalogue

Cite this

Gleiss, P. M., Leydold, J., & Stadler, P. F. (2001). Circuit Bases of Strongly Connected Digraphs. (April 2001 ed.) Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business. Preprint Series / Department of Applied Statistics and Data Processing No. 40 https://doi.org/10.57938/8d53d6da-88c5-4bed-8985-24c77bfe021f

@techreport{8d53d6da88c54bed898524c77bfe021f,

title = "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. (author's abstract)",

author = "Gleiss, {Petra M.} and Josef Leydold and Stadler, {Peter F.}",

year = "2001",

doi = "10.57938/8d53d6da-88c5-4bed-8985-24c77bfe021f",

language = "English",

series = "Preprint Series / Department of Applied Statistics and Data Processing",

number = "40",

publisher = "Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business",

edition = "April 2001",

type = "WorkingPaper",

institution = "Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business",

}

Gleiss, PM, Leydold, J & Stadler, PF 2001 'Circuit Bases of Strongly Connected Digraphs' Preprint Series / Department of Applied Statistics and Data Processing, no. 40, April 2001 edn, Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business, Vienna. https://doi.org/10.57938/8d53d6da-88c5-4bed-8985-24c77bfe021f

TY - UNPB

T1 - Circuit Bases of Strongly Connected Digraphs

AU - Gleiss, Petra M.

AU - Leydold, Josef

AU - Stadler, Peter F.

PY - 2001

Y1 - 2001

N2 - 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)

AB - 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)

U2 - 10.57938/8d53d6da-88c5-4bed-8985-24c77bfe021f

DO - 10.57938/8d53d6da-88c5-4bed-8985-24c77bfe021f

M3 - WU Working Paper

T3 - Preprint Series / Department of Applied Statistics and Data Processing

BT - Circuit Bases of Strongly Connected Digraphs

PB - Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business

CY - Vienna

ER -