| Abstract |
|---|
| We propose compact routing schemes having space and time complexitiescomparable to a 2-Interval Routing Scheme for the whole class ofnetworks decomposable as Layered Cross Product (LCP) of rooted trees.As a consquence, we design a 'quasi' 2-Interval Routing Scheme forbutterflies, meshes of trees and fat trees.Then we extend our scheme to a class of networks slightly larger than the LCP of trees. Finally, we show that a compact routing scheme for networks which are LCP of general cyclic graphs cannot be found by any method using only information about shortest paths on the factors. |
| Contact |
| Tiziana Calamoneri Dipartimento di Scienze dell'Informazione,Universita' di Roma "La Sapienza",via Salaria, 113,I-OO198, ROME, ITALY calamo@dsi.uniroma1.it |