CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishIn 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.
| Autori interni: | |
| Autori: | BARCACCIA P; BONUCCELLI M |
| Titolo: | POLYNOMIAL-TIME OPTIMAL-ALGORITHMS FOR TIME-SLOT ASSIGNMENT OF VARIABLE BANDWIDTH SYSTEMS |
| Anno del prodotto: | 1994 |
| Digital Object Identifier (DOI): | 10.1109/90.311622 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11568/29499
Copyright © 2021