A Linear Algorithm for Finding the Center of a Unicyclic Graph
Sandra Hedetniemi, Stephen Hedetniemi, Terry Beyer
Committee:
Technical Report(May 1980)
Keywords:

A unicyclic graph G = (V,E) with N vertices is a connected graph which has exactly one cycle (or equivalently, is connected and has N edges). These graphs occur frequently as the topology of computer or switching networks with ring structures. In this paper an O(N) algorithm is presented for finding the center of any unicyclic graph with N vertices. This algorithm uses a divide-and-conquer strategy, along with a bucket (or radix} sort and a system of pointers to avoid the O(N2) to O(N3) computations normally required to find the center of an arbitrary graph.