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

25 Scopus citations

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(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
Volume74
Issue number1-2
DOIs
StatePublished - Apr 30 2000

Keywords

  • 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

Fingerprint 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