@inproceedings{286c4d067b0745eaa0fc0b5499d3abab,
title = "The cent-dian path problem on tree networks",
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.",
keywords = "Centre path, Facility location, Median path",
author = "Becker, {Ronald I.} and Chiang, {Yen I.} and Isabella Lari and Andrea Scozzari",
year = "2001",
doi = "10.1007/3-540-45678-3_63",
language = "英语",
isbn = "3540429859",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "743--755",
booktitle = "Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings",
note = "12th International Symposium on Algorithms and Computation, ISAAC 2001 ; Conference date: 19-12-2001 Through 21-12-2001",
}