Minimal Cycle Bases of Outerplanar Graphs
The Electronic Journal of CombinatoricsPublished 27 February 1998Open access
Josef Leydold, Peter F. Stadler
Citations51
SJR quartileQ1
SJR score0.90
SNIP1.15
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Two-connected outerplanar graphs have a unique minimal cycle basis with length $2|E|-|V|$.
Abstract
2-connected outerplanar graphs have a unique minimal cycle basis with length $2\vert E\vert-\vert V\vert$. They are the only Hamiltonian graphs with a cycle basis of this length.
Keywords
Computer ScienceEngineering
Proceedings of the National Academy of SciencesImproved free-energy parameters for predictions of RNA duplex stability.
1,493 Citations1986Susan M. Freier, Ryszard Kierzek +5 more
These parameters predict melting temperatures of most oligonucleotide duplexes within 5 degrees C, about as good as can be expected from the nearest-neighbor model.
Annalen der PhysikUeber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird
1,212 Citations1847G. Kirchhoff
American Journal of MathematicsOn the Abstract Properties of Linear Dependence
709 Citations1935Hassler Whitney
Birkhäuser Boston eBooksOn the Abstract Properties of Linear Dependence1
667 Citations2009Hassler Whitney
Graphs: Theory and Algorithms
372 Citations1992K. Thulasiraman, M.N.S. Swamy
This book discusses Graphs and Vector Spaces, which are concerned with the construction of graphs, and some of the algorithms used to solve these problems.
SIAM Journal on ComputingA Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
275 Citations1987Joseph D. Horton
An algorithm is given that finds a cycle basis with the shortest possible length in $O(m^3 n)$ operations, which is the first known polynomial-time algorithm for this problem.
Journal of Chemical Information and Computer SciencesReview of ring perception algorithms for chemical graphs
187 Citations1989Geoffrey M. Downs, Valerie J. Gillet +2 more
In this review, the various published ring perception algorithms are classified according to the initial ring set obtained, and each algorithm or method of perception is described in detail.
ACM Transactions on Mathematical SoftwareAlgorithms for Generating Fundamental Cycles in a Graph
118 Citations1982Narsingh Deo, G. M. Prabhu +1 more
It is shown that for regular graphs of order n the expected value of the total length of a minimum fundamentalcycle set does not exceed O(n2).
The Electronic Journal of CombinatoricsUnion of all the Minimum Cycle Bases of a Graph
65 Citations1997Philippe Vismara
A polynomial algorithm is presented that computes a compact representation of the potentially exponential-sized set ${\cal C_R}$ in $O(\nu m^3)$ (where $\nu$ denotes the cyclomatic number).
SIAM Journal on Applied MathematicsOn Vector Spaces Associated with a Graph
59 Citations1971Wai‐Kai Chen
Journal of Chemical DocumentationMathematical Basis of Ring-Finding Algorithms in CIDS
41 Citations1971Morris Plotkin
Information Processing LettersOn finding a cycle basis with a shortest maximal cycle
25 Citations1995David M. Chickering, Dan Geiger +1 more
It is shown that any cycle basis B of G such that the sum of the lengths of the cycles included in B is the smallest among all cycle bases of G constitutes a solution to the SMCB problem.
Journal of Graph TheoryIs every cycle basis fundamental?
20 Citations1989David Hartvigsen, Eitan Zemel
A constructive characterization is given that leads to a algorithm that can be used to determine if a graph has a cycle basis that covers every edge two or more times and an equivalent dual characterization for the cutset space is given.
Discrete MathematicsA Family of special outerplanar graphs with only one triangle satisfying the cycle basis interpolation property
2 Citations1995Yan Liu
It is proved that a family of special outerplanar graphs with only one triangle, namely bamboo shoot graphs, have the cbip, which is the length of a cycle basis of a graph G that has the cycle basis interpolation property.