A solvable routing problem
E. N. Gilbert · Networks · 1989
Abstract Stations 1, 2, …,n are interconnected; bij channels join stations i and j. Channels may be grouped together in cables to reruce cost. A Routing problem requires a channel layout (or network of cables) that has minimum cost. The cost of a cable is taken to be independent of its length but a function f(k) of the cable size k. That kind of cost is unusual in practice, but might be appropriate if the “cable” is actually a satellite link. Requiring f(k) to be concave gives a discount for large cables. That imposes a number of special properties on the minimizing network. An extra assumption bij = b, a constant for all i, j, produces a solvable problem. Depending on the shape of f(k), the solution network is either a complete graph or a particular kind of tree.