Algorithms for path medi-centers of a tree

Citation
I. Averbakh et O. Berman, Algorithms for path medi-centers of a tree, COMPUT OPER, 26(14), 1999, pp. 1395-1409
Citations number
14
Categorie Soggetti
Engineering Management /General
Journal title
COMPUTERS & OPERATIONS RESEARCH
ISSN journal
03050548 → ACNP
Volume
26
Issue
14
Year of publication
1999
Pages
1395 - 1409
Database
ISI
SICI code
0305-0548(199912)26:14<1395:AFPMOA>2.0.ZU;2-D
Abstract
We consider the problem of finding an optimal location of a path on a tree: using combinations of minisum and minimax criteria (which are respectively maximal distance and average distance from the path to customers situated at the vertices), The case of linear combination of the two criteria and th e case where one criterion is optimized subject to a restriction on the val ue of the other are considered and linear-time algorithms for these problem s are presented. It is proved that the representation of the set of Pareto- optimal paths in the space of criteria has cardinality not greater than n - 1, where n is the number of vertices of the tree, and can be obtained in O (n log n ) time, although the number of Pareto-optimal paths can be O(n(2)) . (C) 1999 Elsevier Science Ltd. All rights reserved.