Premium
A solvable routing problem
Author(s) -
Gilbert E. N.
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190508
Subject(s) - routing (electronic design automation) , constant (computer programming) , channel (broadcasting) , function (biology) , combinatorics , computer science , graph , tree (set theory) , join (topology) , mathematics , topology (electrical circuits) , mathematical optimization , discrete mathematics , computer network , evolutionary biology , biology , programming language
Stations 1, 2, …, n are interconnected; b ij 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 b ij = 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.