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

Antoine Vigneron, Lixin Gao, Mordecai J. Golin*, Giuseppe F. Italiano, Bo Li

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


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(k2 n3/2), while in the worst case O(k2 n2). Our method employs dynamic programming and uses O(nk) space, while the best known algorithms for undirected trees require O(n2k) space.

Original languageEnglish (US)
Pages (from-to)81-88
Number of pages8
JournalInformation Processing Letters
Issue number1-2
StatePublished - Apr 30 2000
Externally publishedYes


  • Algorithms
  • Analysis of algorithms
  • Combinatorial problems
  • Dynamic programming
  • K-median problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'An algorithm for finding a k-median in a directed tree'. Together they form a unique fingerprint.

Cite this