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 (396kB)


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 11:25
Last Modified: 22 Oct 2019 00:41


View Item View Item


Downloads per month over past year

View more statistics