Algorithms for Generating Fundamental Cycles in a Graph
Narsingh Deo, Gautham Manuru Prabhu, Mukkai S. Krishnamoorthy · ACM Transactions on Mathematical Software · 1982
The following problem is considered: Given an undirected, connected graph G, find a spanning tree in G such that the sum of the lengths of the fundamental cycles (with respect to this tree) is minimum.This problem, besides being interesting in its own right, is useful in a variety of situations It is shown that this problem is NP-complete.A number of polynomial-time, heuristic algorithms which yield "good" suboptimal solutions are presented and their performances are discussed.Finally, 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).