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.

Additional Metadata
Conference 25th Canadian Conference on Computational Geometry, CCCG 2013
Citation
Bose, P, De Carufel, J.-L. (Jean-Lou), Grimm, C. (Carsten), Maheshwari, A, & Smid, M. (2013). Optimal data structures for farthest-point queries in cactus networks. Presented at the 25th Canadian Conference on Computational Geometry, CCCG 2013.