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.
Barcaccia, P; Bonuccelli, MAURIZIO ANGELO
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/29499
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 7
social impact