|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Preprints >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/467
|
| Title: | An Algorithm for finding a k-median in a directed tree |
| Authors: | Vigneron, Antoine
Gao, Lixin
Golin, Mordecai J.
Italiano, Giuseppe F.
Li, Bo |
| Keywords: | Algorithms
Analysis of algorithms
Combinatorial problems
Dynamic programming
k-median problem |
| Issue Date: | 2000 |
| Citation: | Information processing letters, v. 74, 2000, p. 81-88 |
| Abstract: | We consider the problem of finding 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. |
| URI: | http://hdl.handle.net/1783.1/467 |
| Appears in Collections: | CSE Preprints
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| KM.pdf | | 147Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
