An efficient algorithm for the Steiner Tree Problem with revenue, bottleneck and hop objective functions

This paper considers a tricriteria Steiner Tree Problem arising in the design of telecommunication networks. The objective functions consist of maximizing the revenue and of minimizing the maximal distance between each pair of interconnected nodes, as well as the maximal number of arcs between the root and each node. A polynomial algorithm is developed for the generation of a minimal complete set of Pareto-optimal Steiner trees. Optimality proofs are given and computational experience on a set of randomly generated problems is reported.