Minimum cost flow-dependent communication networks

Abstract

In the construction of a communication network, the (Euclidean) length of the network is an important but not unique factor determining the cost of the network. Among many possible network models, Gilbert proposed a flow-dependent model in which flow demands are assigned between each pair of points in a given point set A, and the cost per unit length of a link in the network is a function of the flow through the link. In this article we first investigate the properties of this Gilbert model: the concavity of the cost function, decomposition, local minimality, the number of Steiner points, and the maximum degree of Steiner points. Then we propose three heuristics for constructing minimum cost..