Return to search

Interchangeability of Relevant Cycles in Graphs

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) / Series: Preprint Series / Department of Applied Statistics and Data Processing

Identiferoai:union.ndltd.org:VIENNA/oai:epub.wu-wien.ac.at:epub-wu-01_9e1
Date January 1999
CreatorsGleiss, Petra M., Leydold, Josef, Stadler, Peter F.
PublisherDepartment of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business
Source SetsWirtschaftsuniversität Wien
LanguageEnglish
Detected LanguageEnglish
TypePaper, NonPeerReviewed
Formatapplication/pdf
Relationhttp://epub.wu.ac.at/898/

Page generated in 0.0016 seconds