A linear-time algorithm for solving the center problem on weighted cactus graphs

For a nontrivial graph G(V,E) , the distance d(u,v) between vertices u and v is the length of a shortest path p(u,v) in G if such a path exists. The eccentricity e(u) of a vertex u in a graph is the distance from u to a vertex furthest from u . That is, e(u)= max {d(u,v)∣v∈V} . The radius of a graph G is defined as min {e(u)∣u∈V} . A center of G is a vertex whose eccentricity is equal to the radius. The center problem is to find all centers of a graph. In this paper, we shall study the center problem on weighted cactus graphs, and develop an optimal algorithm.