Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

A note on fundamental, non-fundamental, and robust cycle bases

 
: Klemm, K.; Stadler, P.F.

:

Dress, A.:
Networks in computational biology. Special issue : Based on a workshop in Ankara, Turkey, September 10 - 12, 2006
Amsterdam: Elsevier, 2009 (Discrete applied mathematics 157.2009, Nr.10)
ISSN: 0166-218X
pp.2432-2438
Workshop Networks in Computational Biology <2006, Ankara>
English
Conference Paper, Journal Article
Fraunhofer IZI ()

Abstract
In many biological systems, robustness is achieved by redundant wiring, and reflected by the presence of cycles in the graphs connecting the systems' components. When analyzing such graphs, cyclically robust cycle bases of are of interest since they can be used to generate all cycles of a given 2-connected graph by iteratively adding basis cycles. It is known that strictly fundamental (or Kirchhoff) bases, i.e., those that can be derived from a spanning tree, are not necessarily cyclically robust. Here we note that, conversely, cyclically robust bases (even of planar graphs) are not necessarily fundamental. Furthermore, we present a class of cubic graphs for which cyclically robust bases can be explicitly constructed.

: http://publica.fraunhofer.de/documents/N-101798.html