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.