Abstract
An ℓ-core of a tree T=(V,E) with |V|=n, is a path P with length at most ℓ that is central with respect to the property of minimizing the sum of the distances from the vertices in P to all the vertices of T not in P. The distance between two vertices is the length of the shortest path joining them. In this paper we present efficient algorithms for finding the ℓ-core of a tree. For unweighted trees we present an O(nℓ) time algorithm, while for weighted trees we give a procedure with time complexity of O(n log2 n). The algorithms use two different types of recursive principle in their operation.
Original language | English |
---|---|
Pages (from-to) | 25-42 |
Number of pages | 18 |
Journal | Discrete Applied Mathematics |
Volume | 118 |
Issue number | 1-2 |
DOIs | |
State | Published - 01 09 2002 |
Externally published | Yes |
Keywords
- Core
- Facility location
- Median problems