Constructing minimum cost flow-dependent networks

Abstract

In the construction of a communication network, the 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 paper 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 Gilbert networ..