HKUST Institutional Repository >
Computer Science and Engineering >
CSE Preprints >
Please use this identifier to cite or link to this item:
|Title: ||An Algorithm for finding a k-median in a directed tree|
|Authors: ||Vigneron, Antoine|
Golin, Mordecai J.
Italiano, Giuseppe F.
Analysis of algorithms
|Issue Date: ||2000 |
|Citation: ||Information processing letters, v. 74, 2000, p. 81-88|
|Abstract: ||We consider the problem of ﬁnding a k-median in a directed tree. We present an algorithm that computes a k-median in O(Pk2) 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(k2n log n) time, in a random tree O(k2n3/2), while in the worst case O(k2n2). Our method employs dynamic programming and uses O(nk) space, while the best known algorithms for undirected trees require O(n2k) space.|
|Appears in Collections:||CSE Preprints|
Files in This Item:
All items in this Repository are protected by copyright, with all rights reserved.