This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  1997, with author Gaibisso C., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 455  (Next) 


Becchetti L., Carlo Gaibisso

Lower bounds for the virtual path layout problem in ATM networks

ABSTRACT

In this paper we address the problem of designing Virtual Path Layouts with fixed hop count. In this framework we derive a lower bound for networks with arbitrary topology and arbitrary sets of connection requests. We then restrict our attention to the broadcast (from one node in the network to all other nodes) and to the all-to-all (between all pairs of nodes) communication patterns, applying the general lower bound to characterize the complexity of these problems for some important classes of graphs, including planar graphs and graphs with bounded treewidth. We finally test the effectiveness of our result deriving lower bounds for some particular topologies (trees, trees of rings and meshes) for which both lower bounds and upper bounds are known.