Tight bounds for oblivious routing in the hypercube |
| |
| Authors: | Christos Kaklamanis Danny Krizanc Thanasis Tsantilas |
| |
| Affiliation: | (1) Aiken Computation Laboratory, Harvard University, 02138 Cambridge, MA, USA;(2) Department of Computer Science, University of Rochester, 14627 Rochester, NY, USA;(3) Present address: Department of Computer Science, Columbia University, 10027 New York, NY, USA |
| |
| Abstract: | We prove that in anyN-node communication network with maximum degreed, any deterministic oblivious algorithm for routing an arbitrary permutation requires  ( N/d) parallel communication steps in the worst case. This is an improvement upon the (N/d3/2) bound obtained by Borodin and Hopcroft. For theN-node hypercube, in particular, we show a matching upper bound by exhibiting a deterministic oblivious algorithm that routes any permutation in  (N/logN) steps. The best previously known upper bound was (N). Our algorithm may be practical for smallN (up to about 214 nodes).C. Kaklamanis was supported in part by NSF Grant NSF-CCR-87-04513. T. Tsantilas was supported in part by NSF Grants NSF-DCR-86-00379 and NSF-CCR-89-02500. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
