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. © 2001 Springer Berlin Heidelberg.
The cent-dian path problem on tree networks / Ronald I., Becker; Yen I., Chiang; Lari, Isabella; Scozzari, Andrea. - STAMPA. - 2223 LNCS:(2001), pp. 743-755. (Intervento presentato al convegno 12th International Symposium on Algorithms and Computation, ISAAC 2001 tenutosi a Christchurch nel 19 December 2001 through 21 December 2001) [10.1007/3-540-45678-3_63].
The cent-dian path problem on tree networks
LARI, Isabella;SCOZZARI, Andrea
2001
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. © 2001 Springer Berlin Heidelberg.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.