Finding the ℓ-core of a tree

Ronald I. Becker, Yen I. Chang, Isabella Lari, Andrea Scozzari, Giovanni Storchi*

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

17 Scopus citations

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 languageEnglish
Pages (from-to)25-42
Number of pages18
JournalDiscrete Applied Mathematics
Volume118
Issue number1-2
DOIs
StatePublished - 01 09 2002
Externally publishedYes

Keywords

  • Core
  • Facility location
  • Median problems

Fingerprint

Dive into the research topics of 'Finding the ℓ-core of a tree'. Together they form a unique fingerprint.

Cite this