Tim Carnes
Harvey Mudd College Mathematics 2005
| Thesis: | Permutation Routing in the Hypercube and Grid Topologies |
|---|---|
| Thesis Advisor: | Prof. Ran Libeskind-Hadas |
| Second Reader: | Prof. Francis E. Su |
| E-Mail: | tcarnes@hmc.edu |
| Poster: | HMC Presentation Days Poster |
| Presentation: | HMC Presentation Days Slides |
Permutation Routing in the Hypercube and Grid Topologies
The problem of edge-disjoint path routing arises from applications in distributed memory parallel computing. We examine this problem in both the directed hypercube and two-dimensional grid topologies. Complexity results are obtained for these problems where the routing must consist entirely of shortest-length paths. Additionally, approximation algorithms are presented for the case when the routing request is of a special form known as a permutation. Permutations simply require that no vertex in the graph may be used more than once as either a source or target for a routing request. Szymanski conjectured that permutations are always routable in the directed hypercube, and this remains an open problem.