Resource title

Interchangeability of Relevant Cycles in Graphs

Resource image

image for OpenScout resource :: Interchangeability of Relevant Cycles in Graphs

Resource description

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

Resource author

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

Resource publisher

Resource publish date

Resource language


Resource content type


Resource resource URL

Resource license

Adapt according to the license agreement. Always reference the original source and author.