COMPUTING THE 2-MEDIAN ON TREE NETWORKS IN O(N-LG-N) TIME

被引：40

作者：

GAVISH, B ^{[1
]}

SRIDHAR, S ^{[1
]}

机构：

[1] USN,POSTGRAD SCH,DEPT SYST MANGAEMENT,MONTEREY,CA 93943

来源：

NETWORKS | 1995年 / 26卷 / 04期

关键词：

D O I：

10.1002/net.3230260413

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 I-median and the 2-medians in tree networks, and the properties inherent in tree structure, an improved algorithm is developed for computing the e-median. The time complexity of this algorithm is O(n lg n). The details of the algorithm are described along with an illustrative example. (C) 1995 John Wiley & Sons, Inc.

引用

页码：305 / 317

页数：13