Graduation Year
2005
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Ran Libeskind-Hadas (CS)
Reader 2
Francis Edward Su
Abstract
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.
Recommended Citation
Carnes, Tim Alan, "Permutation Routing in the Hypercube and Grid Topologies" (2005). HMC Senior Theses. 168.
https://scholarship.claremont.edu/hmc_theses/168
Thesis Proposal
Tim Carnes.jpg (5 kB)
Picture of Tim Carnes
tcarnes-2005-thesis-poster.pdf (983 kB)
Presentation Poster
tcarnes-presentation.pdf (2207 kB)
Presentation Slides
