Optimal Data Structures for Farthest-Point Queries in Cactus Networks

Abstract

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 Θ(logn) time for cycles, and in Θ(k + logn) time for uni-cyclic networks and cactus networks, where n is the size of the network and k is the number of farthest-points.