Premium
Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry
Author(s) -
Akl S. G.,
Qiu K.,
Stojmenović I.
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230403
Subject(s) - hypercube , computer science , interconnection , algorithm , star (game theory) , computational geometry , topology (electrical circuits) , parallel algorithm , star network , network topology , theoretical computer science , parallel computing , mathematics , computer network , combinatorics , mathematical analysis , ring network
The star and pancake networks were recently proposed as attractive alternatives to the hypercube topology for interconnecting processors in a parallel computer. However, few parallel algorithms are known for these networks. In this paper, we present several data communication schemes and basic algorithms for these two networks. These algorithms are then used to develop parallel solutions to various computational geometric problems on both networks. Computational geometry is just one area where the algorithms proposed here can be applied. Indeed, we believe that these algorithms are interesting and important in their own right and are fundamental to the design of solutions on the star and pancake networks to a host of other problems. © 1993 by John Wiley & Sons, Inc.