Please use this identifier to cite or link to this item:

An algorithm for finding a k-median 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, (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.
ISSN 0020-0190
Language English
Format Article
Access View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
KM.pdf 151247 B Adobe PDF