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 cr to a vertex furthest from Ir. That is, e(u) = max{d(rc, v) \ v is an element of V}. The radius of a graph G is defined as min{e(u) \ u is an element of 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 shah study the center problem on weighted cactus graphs, and develop an optimal algorithm. (C) 1999 Elsevier Science B.V. All rights reserved.
algorithms center weighted cactus graphs furthest neighbor diameter