Finding the ℓ-core of a tree

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

doi:10.1016/S0166-218X(01)00254-2

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

19 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 language	English
Pages (from-to)	25-42
Number of pages	18
Journal	Discrete Applied Mathematics
Volume	118
Issue number	1-2
DOIs	https://doi.org/10.1016/S0166-218X(01)00254-2
State	Published - 01 09 2002
Externally published	Yes

Keywords

Core
Facility location
Median problems

Access to Document

10.1016/S0166-218X(01)00254-2

Cite this

@article{63121e6efd8c423bb16d9a8c03724640,

title = "Finding the ℓ-core of a tree",

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

keywords = "Core, Facility location, Median problems",

author = "Becker, \{Ronald I.\} and Chang, \{Yen I.\} and Isabella Lari and Andrea Scozzari and Giovanni Storchi",

year = "2002",

month = sep,

day = "1",

doi = "10.1016/S0166-218X(01)00254-2",

language = "英语",

volume = "118",

pages = "25--42",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Finding the ℓ-core of a tree

AU - Becker, Ronald I.

AU - Chang, Yen I.

AU - Lari, Isabella

AU - Scozzari, Andrea

AU - Storchi, Giovanni

PY - 2002/9/1

Y1 - 2002/9/1

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

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

KW - Core

KW - Facility location

KW - Median problems

UR - https://www.scopus.com/pages/publications/84867945936

U2 - 10.1016/S0166-218X(01)00254-2

DO - 10.1016/S0166-218X(01)00254-2

M3 - 文章

AN - SCOPUS:84867945936

SN - 0166-218X

VL - 118

SP - 25

EP - 42

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-2

ER -

Finding the ℓ-core of a tree

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this