POLYNOMIAL-TIME OPTIMAL-ALGORITHMS FOR TIME-SLOT ASSIGNMENT OF VARIABLE BANDWIDTH SYSTEMS

In this paper, we consider the optimal (i.e., minimum length) time slo t assignment problem for variable bandwidth switching systems. Existin g algorithms for this problem are known to be pseudo-polynomial. The p ractical question of finding a fast optimal algorithm, as well as the theoretical question of whether the above problem is NP-complete were left open. We present here a technique to show polynomial time complex ity of some time slot assignment algorithms. Such a technique applies to an algorithm proposed by Chalasani and Varma in 1991 (called CV alg orithm), as well as to a network how based optimal algorithm, proposed here for the first time. CV algorithm and the one proposed here are s lightly different. Thus, we give an answer to both the above questions , by establishing that the problem is in P, and by showing effective a lgorithms for it.