HKUST Library Institutional Repository Banner

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 ļ¬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.
URI: http://hdl.handle.net/1783.1/467
Appears in Collections:CSE Preprints

Files in This Item:

File Description SizeFormat
KM.pdf147KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.