Optimal Data Structures for Farthest-Point Queries in Cactus Networks
Vol. 19, no. 1, pp. 11-41, 2015. Regular paper.
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.
Submitted: August 2014.
Reviewed: November 2014.
Revised: December 2014.
Accepted: December 2014.
Final: January 2015.
Published: January 2015.
Communicated by Stephen G. Kobourov
article (PDF)