Algorithms for Finding Diameter Cycles of Biconnected Graphs

Abstract

In this paper, we first coin a new graph theoretic problem called the diameter cycle problem with numerous applications. A longest cycle in a graph G = (V, E) is referred to as a diameter cycle of G iff the distance in G of every vertex on the cycle to the rest of the on-cycle vertices is maximal. We then present two algorithms for finding a diameter cycle of a biconnected graph. The first algorithm is an abstract intuitive algorithm that utilizes a brute-force mechanism for expanding an initial cycle by repeatedly replacing paths on the cycle with longer paths. The second algorithm is a concrete algorithm that uses fundamental cycles in the expansion process and has the time and space complexity of O(n^6) and O(n^2), respectively. To the best of our knowledge, this problem was neither defined nor addressed in the literature. The diameter cycle problem distinguishes itself from other cycle finding problems by identifying cycles that are maximally long while maximizing the distances between vertices in the cycle. Existing cycle finding algorithms such as fundamental and longest cycle algorithms do not discover cycles where the distances between vertices are maximized while also maximizing the length of the cycle.