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

en

Resource content type

application/pdf

Resource resource URL

http://epub.wu.ac.at/898/1/document.pdf

Resource license

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