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

We consider the problem of finding a k-median in a directed tree. We present an algorithm that computes a k-median in O(P k 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