An O (log N ) deterministic packet-routing scheme
Author:
Open Access
- 2 January 1992
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 39 (1) , 55-70
Abstract
A deterministic O (log N )-time algorithm for the problem of routing an aribitrary permutation on an N -processor bounded-degree network with bounded buffers is presented. Unlike all previous deterministic solutions to this problem, our routing scheme does not reduce the routing problem to sorting and does not use the sorting network of Ajtai, et al. [1]. Consequently, the constant in the run time of our routing scheme is substantially smaller, and the network topology is significantly simpler.Keywords
This publication has 8 references indexed in Scilit:
- Improved sorting networks withO(logN) depthAlgorithmica, 1990
- Eigenvalues and expandersCombinatorica, 1986
- Explicit expanders and the Ramanujan conjectures1986
- Routing, merging, and sorting on parallel models of computationJournal of Computer and System Sciences, 1985
- Expanders, sorting in rounds and superconcentrators of limited depth1985
- Explicit Concentrators from Generalized N-GonsSIAM Journal on Algebraic Discrete Methods, 1984
- Tight bounds on the complexity of parallel sorting1984
- An 0(n log n) sorting network1983