Geodesic
Interchangeability of relevant cycles in graphs
The electronic journal of combinatorics, Tome 7 (2000)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The set ${\cal R}$ of relevant cycles of a graph $G$ is the union of its minimum cycle bases. We introduce a partition of ${\cal R}$ such that each cycle in a class ${\cal W}$ can be expressed as a sum of other cycles in ${\cal W}$ and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class ${\cal 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.
DOI : 10.37236/1494
Classification : 05C38, 92E10, 05C85, 92D20
Mots-clés : minimum cycle basis, relevant cycles 
@article{10_37236_1494,
     author = {Petra M. Gleiss and Josef Leydold and Peter F. Stadler},
     title = {Interchangeability of relevant cycles in graphs},
     journal = {The electronic journal of combinatorics},
     year = {2000},
     volume = {7},
     doi = {10.37236/1494},
     zbl = {0939.05048},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1494/}
}
TY  - JOUR
AU  - Petra M. Gleiss
AU  - Josef Leydold
AU  - Peter F. Stadler
TI  - Interchangeability of relevant cycles in graphs
JO  - The electronic journal of combinatorics
PY  - 2000
VL  - 7
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1494/
DO  - 10.37236/1494
ID  - 10_37236_1494
ER  - 
%0 Journal Article
%A Petra M. Gleiss
%A Josef Leydold
%A Peter F. Stadler
%T Interchangeability of relevant cycles in graphs
%J The electronic journal of combinatorics
%D 2000
%V 7
%U http://geodesic.mathdoc.fr/articles/10.37236/1494/
%R 10.37236/1494
%F 10_37236_1494
Petra M. Gleiss; Josef Leydold; Peter F. Stadler. Interchangeability of relevant cycles in graphs. The electronic journal of combinatorics, Tome 7 (2000). doi: 10.37236/1494

Cité par Sources :