We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Complete Characterization of the Path Layout Construction Problem for ATM Networks with Given Hop Count and Load.
- Authors
Eilam, Tamar; Flammini, Michele; Zaks, Shmuel
- Abstract
We investigate the time complexity of deciding the existence of layouts of virtual paths in high-speed networks, that enable a connection from one vertex to all others and have maximum hop count h and maximum edge load l, for a stretch factor of one. We prove that the problem of determining the existence of such layouts is NP-complete for every given values of h and l, except for the cases h = 2, l = 1 and h = 1, any l, for which we give polynomial-time layout constructions. Extensions for cases of a stretch factor greater than one are also discussed.
- Publication
Parallel Processing Letters, 1998, Vol 8, Issue 2, p207
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626498000225