A solvable routing problem

✍ Scribed by E. N. Gilbert

• Publisher: John Wiley and Sons
• Year: 1989
• Tongue: English
• Weight: 337 KB
• Volume: 19
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230190508

✦ Synopsis

Stations 1,2, . . . ,n are interconnected; b,, channels join stations i and j . Channels may be grouped together in cables to reduce 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 functionf(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. Requiringf(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,, = b, a constant for all i, j , produces a solvable problem.

Depending on the shape off#), the solution network is either a complete graph or a particular kind of tree.