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

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

doi:10.1016/s0020-0190(00)00026-0

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 journal › Article › peer-review

26 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(Pk²) 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²n log n) time, in a random tree O(k² n^3/2), while in the worst case O(k² n²). Our method employs dynamic programming and uses O(nk) space, while the best known algorithms for undirected trees require O(n²k) space.

Original language	English (US)
Pages (from-to)	81-88
Number of pages	8
Journal	Information Processing Letters
Volume	74
Issue number	1-2
DOIs	https://doi.org/10.1016/s0020-0190(00)00026-0
State	Published - Apr 30 2000
Externally published	Yes

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

Access to Document

10.1016/s0020-0190(00)00026-0

Cite this

@article{f74c3a883df447ada1822da95476a024,

title = "An algorithm for finding a k-median in a directed tree",

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.",

keywords = "Algorithms, Analysis of algorithms, Combinatorial problems, Dynamic programming, K-median problem",

author = "Antoine Vigneron and Lixin Gao and Golin, {Mordecai J.} and Italiano, {Giuseppe F.} and Bo Li",

year = "2000",

month = apr,

day = "30",

doi = "10.1016/s0020-0190(00)00026-0",

language = "English (US)",

volume = "74",

pages = "81--88",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "1-2",

}

TY - JOUR

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

AU - Vigneron, Antoine

AU - Gao, Lixin

AU - Golin, Mordecai J.

AU - Italiano, Giuseppe F.

AU - Li, Bo

PY - 2000/4/30

Y1 - 2000/4/30

N2 - 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.

AB - 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.

KW - Algorithms

KW - Analysis of algorithms

KW - Combinatorial problems

KW - Dynamic programming

KW - K-median problem

UR - http://www.scopus.com/inward/record.url?scp=0033738251&partnerID=8YFLogxK

U2 - 10.1016/s0020-0190(00)00026-0

DO - 10.1016/s0020-0190(00)00026-0

M3 - Article

AN - SCOPUS:0033738251

SN - 0020-0190

VL - 74

SP - 81

EP - 88

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1-2

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this