Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/467

An algorithm for finding a k-median in a directed tree

Authors Vigneron, A
Gao, LX
Golin, MJ
Italiano, GF
Li, B
Issue Date 2000
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.
Subjects
ISSN 0020-0190
Language English
Format Article
Access View full-text via Web of Science
View full-text via Scopus
Find@HKUST
Files in this item:
File Description Size Format
KM.pdf 151247 B Adobe PDF