In this paper, we consider 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. We present here 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 CV algorithm), as well as to a network flow based optimal algorithm, proposed here for the first time. CV algorithm and the one proposed here are slightly different. Thus, we give an answer to both the above questions, by establishing that the problem is in P, and by showing effective algorithms for it.
POLYNOMIAL-TIME OPTIMAL-ALGORITHMS FOR TIME-SLOT ASSIGNMENT OF VARIABLE BANDWIDTH SYSTEMS
BONUCCELLI, MAURIZIO ANGELO
1994
Abstract
In this paper, we consider 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. We present here 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 CV algorithm), as well as to a network flow based optimal algorithm, proposed here for the first time. CV algorithm and the one proposed here are slightly different. Thus, we give an answer to both the above questions, by establishing that the problem is in P, and by showing effective algorithms for it.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
