The Matching Model for Routing Permutations on Graphs

A Senior Project Submitted to the Division of Natural Sciences and Mathematics of Bard College

by Rodney Waldhoff

Annandale-on-Hudson, New York

May 1997

This paper is an outgrowth of my senior project research at Bard College. It is available here for personal perusal and printing, and is copyright (c) 1997 by me, Rod Waldhoff.

The paper explores a model for parallel processing introduced by Noga Alon, Fan Chung and Ronald Graham in the SIAM Journal of Discrete Mathematics (Vol. 7, No. 3, August 1994, p. 513-530) in a paper entiled "Routing Permutations on Graphs via Matchings".

You can read the abstract online for a brief description of the model and the paper.

Or, you can just download the whole thing as a postscript (.ps) file.

Finally, you could drive, fly or walk to New York's scenic Hudson Valley, go to the Bard's Stevenson Library, and read it there.

There are some related papers available on-line, and several others in the literature.

Here are some of the papers available via ftp:

• Many-to-Many Routing on Trees via Matchings
  Pantziou, Grammati E.; Roberts, Alan; Symvonis, Antonis
  ftp://theory.doc.ic.ac.uk/tfm/papers/0by-country/AU/Sydney/CS-Reports/TR96_507.ps.Z

• On the Hot-Potato Permutation Routing Algorithm of Borodin, Rabani and Schieber
  Plunkett, Richard Thomas; Symvonis, Antonis
  ftp://theory.doc.ic.ac.uk/tfm/papers/0by-country/AU/Sydney/CS-Reports/TR95_500.ps.Z

• Routing on Trees via Matchings
  Roberts, Alan; Symvonis, Antonis; Zhang, Louxin
  from Lecture Notes of Computer Science, Vol 955: 4th Workshop on Algorithms and Data Structures, pgs 251-262, 1995.
  ftp://theory.doc.ic.ac.uk/tfm/papers/0by-country/AU/Sydney/CS-Reports/TR95_494.ps.Z

• Permutation Routing via Matchings
  Hoyer, Peter; Larsen, Kim S.
  Odense University Web Site (sorry, can't remember the URL).

Back to my main page.
Back to my portfolio.
Back to my resume.