Mapping Cycles and Trees on Wrap-Around Butterfly Graphs
Meghanad D. Wagh, Osman Guzide · SIAM Journal on Computing · 2005
We give a new algebraic representation for the wrap-around butterfly interconnection network. This new representation is based on the direct product of groups and finite fields and allows an algebraic expression of the network connectivity. The abstract algebraic tools may then be employed to explore the structural properties of the butterfly. In this paper we exploit this model to map guest graphs on the butterfly. In particular, we provide designs of unit dilation mappings of all possible length cycles on butterflies. We also map the largest possible binary trees on butterfly networks with a dilation 2 if the network degree is less than 16, 3 if it is less than 32, and 4 if it is less than 64. This is a great improvement over previous results.