Premium
Computing the 2‐median on tree networks in O(n lg n) time
Author(s) -
Gavish Bezalel,
Sridhar Suresh
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230260413
Subject(s) - median , tree (set theory) , time complexity , computer science , algorithm , running time , mathematics , combinatorics , geometry
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.