Interchangeability of Relevant Cycles in Graphs

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

Publikation: Working/Discussion PaperWU Working Paper

2 Downloads (Pure)

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. (author's abstract)
OriginalspracheEnglisch
ErscheinungsortVienna
HerausgeberDepartment of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business
PublikationsstatusVeröffentlicht - 1999

Publikationsreihe

NamePreprint Series / Department of Applied Statistics and Data Processing
Nr.27

WU Working Paper Reihe

  • Preprint Series / Department of Applied Statistics and Data Processing

Dieses zitieren