A given system of communication centres C1, C2, . . . , Cn has to be embedded into a given undirected network N. The centres exchange messages at given rates per time unit through a selected routing pattern. If there is no direct connection between Ci and Cj, the messages sent from Ci to Cj pass through several intermediate centres. The messages exchanged between Ci and Cj may be sent along a single path or they may be split into several parts, each part being sent along its own path. The goal is to find an embedding of the centres into the network and a routing pattern which minimizes the maximum intermediate traffic over all centres. The paper deals mainly with the single path model. The complexity of the problem is fully discussed, drawing a sharp borderline 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.
