×

Augmenting Euclidean networks - the Steiner case. (English) Zbl 0584.94029

On a Euclidean plane, a network and n points are given. It is required to interconnect the points and the network by links of minimal total length. The use of Steiner points is allowed, and connections can be made anywhere along the edges or to the vertices of the network. We prove that the problem can be solved in finite time by methods similar to those used for the Euclidean Steiner tree problem. The problem can be generalized to include flow dependent costs for the various links, or to allow for the connection of several networks. However, even in the form discussed in this paper, it may be useful for problems such as connecting new customers to existing networks (for example, computers, telecommunication, electricity, water, sewage disposal), especially if the projected flow between the points and the network does not justify more than the minimal possible investment.

MSC:

94C15 Applications of graph theory to circuits and networks
90B10 Deterministic network models in operations research
Full Text: DOI