Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Adjacency Matrix
Spanning Tree
Related Publications
(2)
Graph theory with applications to engineering and computer science
A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs
Subscribe
Academic
Publications
Algorithms for finding a fundamental set of cycles for an undirected linear graph
Algorithms for finding a fundamental set of cycles for an undirected linear graph,10.1145/363848.363861,Communications of The ACM,C. G. Gotlieb,Derek
Edit
Algorithms for finding a fundamental set of cycles for an undirected linear graph
(
Citations: 14
)
BibTex

RIS

RefWorks
Download
C. G. Gotlieb
,
Derek G. Corneil
Given the
adjacency matrix
of the graph, the algorithm presented in this paper finds a
spanning tree
and then constructs the set of fundamental cycles. Our algorithm is slower than an algorithm presented by Welch by a ratio of N/3 (N is the number of nodes) but requires less storage. For graphs with a large number of nodes and edges, when storage is limited our algorithm is superior to Welch's; however, when the graphs are small, or machine storage is very large, Welch's algorithm is superior. Timing estimates and storage requirements for both methods are presented.
Journal:
Communications of The ACM  CACM
, vol. 10, no. 12, pp. 780783, 1967
DOI:
10.1145/363848.363861
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
portal.acm.org
)
(
doi.acm.org
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(10)
...The set of cycles obtained by inserting each of the remaining edges (chords) of G into T will be a fundamental cycle set of G with respect to T. Thus, the fundamental cycle set of G corresponding to T is a set of cycles (f, g ,… ,f )o f G, each consisting of an edge (f, g )o fGT together with the unique path (g ,… ,f )i nT [
7
,8]...
Georgios Ellinas
,
et al.
PlanarSubgraph and EulerianBased Techniques for Determining Protecti...
...The practical relevance of the MSFCB problem is reflected by numerous computational studies by different groups working in combinatorial optimization ([2,7,8,
11
,15,20])...
Christian Liebchen
,
et al.
Benchmarks for Strictly Fundamental Cycle Bases
...In the literature, a number of algorithms have been proposed and implemented for generating a set of fundamental cycles [3, 7,
8
, 11, 13, 15, 17, 18, 21, 22, 25]...
Narsingh Deo
,
et al.
Algorithms for Generating Fundamental Cycles in a Graph
...In the literature, a number of algorithms have been proposed and implemented for generating a set of fundamental cycles [3, 7,
8
, 11, 13, 15, 17, 18, 21, 22, 25]...
NARSINGH DEO
,
et al.
Algorithms for Generating Cycles in a Graph
...those by Gotlieb and Corneil [
2
] and K~ Patton...
Pentti A. Honkanen
.
Circuit enumeration in an undirected graph
References
(8)
A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs
(
Citations: 22
)
John T. Welch Jr.
Journal:
Journal of The ACM  JACM
, vol. 13, no. 2, pp. 205210, 1966
GIT—a heuristic program for testing pairs of directed line graphs for isomorphism
(
Citations: 41
)
Stephen H. Unger
Journal:
Communications of The ACM  CACM
, vol. 7, no. 1, pp. 2634, 1964
A programming language
(
Citations: 343
)
Kenneth E. Iverson
Published in 1962.
The theory of graphs and its applications alison
(
Citations: 39
)
C. Berge
Published in 1962.
Saaty finite graphs and networks an introduction with applications
(
Citations: 67
)
R. G. Busacker
Published in 1965.
Sort by:
Citations
(14)
Lower bounds for strictly fundamental cycle bases in grid graphs
(
Citations: 1
)
Ekkehard Köhler
,
Christian Liebchen
,
Gregor Wünsch
,
Romeo Rizzi
Journal:
Networks
, vol. 53, no. 2, pp. 191205, 2009
PlanarSubgraph and EulerianBased Techniques for Determining Protection Ring Covers in Mesh Optical Networks
Georgios Ellinas
,
Aklilu GebreyesusHailemariam
Journal:
Journal of Optical Communications and Networking  J OPT COMMUN NETW
, vol. 1, no. 1, pp. 142157, 2009
Benchmarks for Strictly Fundamental Cycle Bases
(
Citations: 2
)
Christian Liebchen
,
Gregor Wünsch
,
Ekkehard Köhler
,
Alexander Reich
,
Romeo Rizzi
Conference:
Workshop on Experimental and Efficient Algorithms  WEA
, pp. 365378, 2007
Parallel algorithms for connectivity problems in graph theory
(
Citations: 2
)
Ratan K. Ghosh
Journal:
International Journal of Computer Mathematics  IJCM
, vol. 18, no. 34, pp. 193218, 1986
Algorithms for Generating Fundamental Cycles in a Graph
(
Citations: 58
)
Narsingh Deo
,
G. M. Prabhu
,
Mukkai S. Krishnamoorthy
Journal:
ACM Transactions on Mathematical Software  TOMS
, vol. 8, no. 1, pp. 2642, 1982