Selection, Routing, and Sorting on the Star Graph

S. Akers, D. Harel, B. Krishnamurthy, 1987, The Star Graph: An attractive alternative to then, Proc. International Conference of Parallel Processing, 393, 400 Akl, 1991, Data Communication and Computational Geometry on the Star and Pancake Interconnection Networks, TR, 91-301 K. Batcher, 1968, Sorting networks and their applications, Proc. AFIPS Spring Joint Comput. Conf, 307, 314 Floyd, 1975, Expected time bounds for selection, Comm. ACM, 18, 165, 10.1145/360680.360691 C. Kaklamanis, D. Krizanc, Th. Tsantilas, 1990, Tight bounds for oblivious routing in the hypercube, Proc. ACM Symposium on Parallel Algorithms and Architectures, 31, 36 Leighton, 1992 A. Menn, A. K. Somani, 1990, An efficient sorting algorithm for the Star Graph interconnection network, Proc. International Conference on Parallel Processing, 3, 1, 8 Nassimi, 1979, Bitonic sort on a mesh connected parallel computer, IEEE Trans. Comput., C28 Palis, 1994, Packet routing and PRAM emulation on Star Graphs and leveled networks, J. Parallel Distrib. Comput., 20, 145, 10.1006/jpdc.1994.1015 S. Rajasekaran, 1993, Mesh connected computers with fixed and reconfigurable buses: Packet routing, sorting and selection, Proc. First Annual European Symposium on Algorithms Rajasekaran, 1995, kkkk, J. Algorithms, 19, 361, 10.1006/jagm.1995.1042 Rajasekaran, 1990, Randomized parallel selection, 472 Rajasekaran, 1993, Derivation of randomized sorting and selection algorithms Rajasekaran, 1993, Random sampling techniques and parallel algorithms design S. Rajasekaran, D. S. L. Wei, 1993, Selection, routing, and sorting on the Star Graph, Proc. International Parallel Processing Symposium Reischuk, 1985, Probabilistic parallel algorithms for sorting and selection, SIAM J. Comput., 14, 396, 10.1137/0214030 Reif, 1987, A logarithmic time sort for linear size networks, J. Assoc. Comput. Mach., 34, 60, 10.1145/7531.7532