Polynomial time optimal algorithms for time slot assignment of variable bandwidth systems

摘要

Considers the optimal (i.e., minimum length) time slot assignment problem for variable bandwidth switching systems. Existing algorithms for this problem are known to be pseudo-polynomial. The practical question of finding a fast optimal algorithm, as well as the theoretical question of whether the above problem is NP-complete were left open. The authors present a technique to show polynomial time complexity of some time slot assignment algorithms. Such a technique applies to an algorithm proposed by Chalasani and Varma in 1991 (called the CV algorithm), as well as to a network flow based optimal algorithm, proposed in the present paper for the first time. The CV algorithm and the one proposed are slightly different. Thus, the authors give an answer to both the above questions, by establishing that the problem is in P, and by showing effective algorithms for it.