Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/467
An algorithm for finding a kmedian in a directed tree
Authors 
Vigneron, Antoine
Gao, Lixin Golin, Mordecai J. Italiano, Giuseppe Francesco Li, Bo 


Issue Date  2000  
Source  Information Processing Letters , v. 74, (12), 2000, APR 30, p. 8188  
Summary  We consider the problem of finding a kmedian in a directed tree. We present an algorithm that computes a kmedian in O(Pk(2)) time where k is the number of resources to be placed and P is the path length of the tree. In the case of a balanced tree, this implies O(k(2)n log n) time, in a random tree O(k(2)n(3/2)), while in the worst case O(k(2)n(2)). Our method employs dynamic programming and uses O(nk) space, while the best known algorithms for undirected trees require O(n(2)k) space. (C) 2000 Elsevier Science B.V. All rights reserved.  
Subjects  
ISSN  00200190  
Language  English 

Format  Article  
Access 
View fulltext via Web of Science View fulltext via Scopus Files in this item:
