A MINIMAX ASSIGNMENT PROBLEM IN TREE-LIKE COMMUNICATION-NETWORKS

A given system of communication centres C-1,C-2,...,C-n has to be embe dded into a given undirected network N. The centres exchange messages at given rates per time unit through a selected routing pattern. If th ere is no direct connection between C-i and C-j, the messages sent fro m C-i to C-j pass through several intermediate centres. The messages e xchanged between C-i and C-j may be sent along a single path or they m ay be split into several parts, each part being sent along its own pat h. The goal is to find an embedding of the centres into the network an d a routing pattern which minimizes the maximum intermediate traffic o ver all centres. The paper deals mainly with the single path model. Th e complexity of the problem is fully discussed, drawing a sharp border line between NP-complete and polynomially solvable cases. In case that N is a tree, a branch and bound algorithm is described and numerical results for random test data are reported and discussed.