99-07-26.pmg-ley-pfs
Interchangeability of Relevant Cycles in Graphs
Abstract
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.
Mathematics Subject Classification:
Primary: 05C38 (paths and cycles).
Secondary: 05C85 (graphic algorithms),
92D20 (protein sequences, DNA sequences),
92E10.
Keywords:
minimum cycle basis, relevant cylces
Download Paper
PostScript |
PDF
[EJC]
Erratum
Josef.Leydold@statistik.wu-wien.ac.at