Computing the 2‐median on tree networks in O(n lg n) time

Abstract

Abstract Location of facilities on tree networks is an important problem in transportation and telecommunication systems. For tree networks, The best‐known algorithm to find 2‐medians has a time complexity of O ( n 2 ). By exploiting the properties relating the 1‐median and the 2‐medians in tree networks, and the properties inherent in tree structure, an improved algorithm is developed for computing the 2‐median. The time complexity of this algorithm is O ( n lg n ). The details of the algorithm are described along with an illustrative example.