The cent-dian path problem on tree networks

Ronald I. Becker, Yen I. Chiang, Isabella Lari, Andrea Scozzari

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

In a network, the distsum of a path is the sum of the distances of all vertices to the path, and the eccentricity is the maximum distance of any vertex to the path. The Cent-dian problem is the constrained optimization problem which seeks to locate on a network a path which has minimalv alue of the distsum over all paths whose eccentricity is bounded by a fixed constant. We consider this problem for trees, and we also consider the problem where an additional constraint is required, namely that the optimal path has length bounded by a fixed constant. The first problem has already been considered in the literature. We give another linear time algorithm for this problem which is considerably simpler than the previous one. The second problem does not seem to have been considered elsewhere, and we give an O(n log2 n) divide-and-conquer algorithm for its solution.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings
Pages743-755
Number of pages13
DOIs
StatePublished - 2001
Externally publishedYes
Event12th International Symposium on Algorithms and Computation, ISAAC 2001 - Christchurch, New Zealand
Duration: 19 12 200121 12 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2223 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Symposium on Algorithms and Computation, ISAAC 2001
Country/TerritoryNew Zealand
CityChristchurch
Period19/12/0121/12/01

Keywords

  • Centre path
  • Facility location
  • Median path

Fingerprint

Dive into the research topics of 'The cent-dian path problem on tree networks'. Together they form a unique fingerprint.

Cite this