Consider the continuum of points on the edges of a network, i.e., a connected, undirected graph with positive edge weights. We measure the distance between these points in terms of the weighted shortest path distance, called the network distance. Within this metric space, we study farthest points and farthest distances. We introduce optimal data structures supporting queries for the farthest distance and the farthest points on trees, cycles, uni-cyclic networks, and cactus networks. Using only linear space and construction time, we support farthest-point queries in Θ(k) time for trees, in Θ(log n) time for cycles, and in Θ(k + log n) time for uni-cyclic networks and cactus networks, where n is the size of the network and k is the number of farthest-points

Additional Metadata
Persistent URL
Journal Journal of Graph Algorithms and Applications
Bose, P, De Carufel, J.-L. (Jean-Lou), Grimm, C. (Carsten), Maheshwari, A, & Smid, M. (2015). Optimal data structures for farthest-point queries in cactus networks. Journal of Graph Algorithms and Applications, 19(1), 11–41. doi:10.7155/jgaa.00345