A minimax assignment problem in treelike communication networks

R.E. Burkard, E. Çela, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
1 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)670-684
Number of pages15
JournalEuropean Journal of Operational Research
Volume87
Issue number3
DOIs
Publication statusPublished - 1995

Fingerprint Dive into the research topics of 'A minimax assignment problem in treelike communication networks'. Together they form a unique fingerprint.

Cite this