An algorithm for finding a k-median in a directed tree
Golin, Mordecai J.
Italiano, Giuseppe Francesco
|Source||Information Processing Letters , v. 74, (1-2), 2000, APR 30, p. 81-88|
|Summary||We consider the problem of finding a k-median in a directed tree. We present an algorithm that computes a k-median 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.|
View full-text via Web of Science
View full-text via Scopus
Files in this item: