Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00345
Optimal Data Structures for FarthestPoint Queries in Cactus Networks
Vol. 19, no. 1, pp. 1141, 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, unicyclic networks, and cactus networks. Using only linear space and construction time, we support farthestpoint queries in Θ(k) time for trees, in Θ(logn) time for cycles, and in Θ(k + logn) time for unicyclic networks and cactus networks, where n is the size of the network and k is the number of farthestpoints.

Submitted: August 2014.
Reviewed: November 2014.
Revised: December 2014.
Accepted: December 2014.
Final: January 2015.
Published: January 2015.
Communicated by
Stephen G. Kobourov
