A service provided by the WU Library and the WU IT-Services

Interchangeability of Relevant Cycles in Graphs

Gleiss, Petra M. and Leydold, Josef and Stadler, Peter F. (1999) Interchangeability of Relevant Cycles in Graphs. Preprint Series / Department of Applied Statistics and Data Processing, 27. Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business, Vienna.

Download (387Kb) | Preview


The set R of relevant cycles of a graph G is the union of its minimum cycle bases. We introduce a partition of R such that each cycle in a class W can be expressed as a sum of other cycles in W and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class W. This result is used to derive upper and lower bounds on the number of distinct minimum cycle bases. Finally, we give a polynomial-time algorithm to compute this partition. (author's abstract)

Item Type: Paper
Additional Information: published in: Electronic J. Comb. 7(1), #R16 (16 pages), 2000
Keywords: minimum cycle basis / relevant cylces
Classification Codes: MSC 05C38, 05C85, 92D20, 92E10
Divisions: Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Depositing User: Repository Administrator
Date Deposited: 10 Jul 2006 13:25
Last Modified: 09 Sep 2015 06:59
URI: http://epub.wu.ac.at/id/eprint/898


View Item