M.Sc Thesis | |

M.Sc Student | Golbandi Nadav |
---|---|

Subject | Characterization and Classification of Butterfly Like Networks |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Ami Litman |

A multistage network is
a Generalized Butterfly Network (GBN) if there are *2 ^{n}*
end-to-end paths, (

This work establishes
several characterizations and properties of the GBN family that were previously
unknown even for the special case of the Butterfly. One characterization is
based on automorphism as follows: A multistage network *G* is a GBN iff it
is 2-regular and for any two end-to-end paths, *P’* and *P’’*, there
is an automorphism of *G* that swaps *p’* and *p’’*. Another one
is based on the existence of paths that shortcut or bypass a certain path and
yet anther is based on a certain symmetry of the distance function. These
results, and all the other results of this work, are founded on the Layered
Cross Product (LCP) introduced by Even and Litman.

It is sometimes useful to assign labels to the vertices or edges of a network. A notable example is the min/max labeling of the edges of a comparator network. To facilitate the study of labeled multistage networks we introduce the Labeled LCP which is an associative and commutative variant of the LCP that operates on vertex-labeled or edge-labeled multistage networks. We show that, under certain conditions, this operator commutes with the concatenation operator. Building on that, we show that the Batcher bitonic sorting network with its min/max labeling is a product of very simple labeled networks - bamboos or rosaries. Moreover, this network, as well as any network which is a product of labeled rosaries under a certain algebra of labels, satisfies a variant of the above path swapping property. Namely, for any two end-to-end paths having identical labels at each stage, there is a label-preserving automorphism that swaps these paths.