On Finding A Cycle Basis With A Shortest Maximal Cycle

The shortest Maximal Cycle Basis (SMCB) problem is that of finding a cycle basis B of a given graph G such that the length of the longest cycle included in B is the smallest among all bases of G. We show 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 the SMCB problem. Finding a basis with the latter property requires at most O (m3n) X steps using Horton’s algorithm where m is the number of edges and n is the number of vertices.