Algorithms for path medi-centers of a tree

Algorithms for path medi-centers of a tree

0.00 Avg rating0 Votes
Article ID: iaor20001982
Country: United Kingdom
Volume: 26
Issue: 14
Start Page Number: 1395
End Page Number: 1409
Publication Date: Dec 1999
Journal: Computers and Operations Research
Authors: ,
Keywords: graphs, networks
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 the case where one criterion is optimized subject to a restriction on the value of the other are considered and linear-time algorithms for these problems 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(n2).

Reviews

Required fields are marked *. Your email address will not be published.