This paper is an outgrowth of my senior project research at Bard College.

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".

A model for routing on connected graphs is investigated. On each vertex of an undirected, connected graph, G=(V,E), is placed a unique "pebble". Each pebble has a destination which is a unique vertex in V, so that the map from a vertex v to the destination of the pebble on v forms a permutation of the vertex set. At each step in the routing, a matching of the edges of G is selected, and the pebbles on the pair of vertices incident with each edge in the matching are interchanged. Our goal is to route all pebbles to their destinations in a minimal number of steps and we define the routing number of a graph, rt(G), to be the maximum number of steps ever required to route a permutation on G with a minimal length routing. The matching model is compared to parallel sorting algorithms and an algorithm for routing on cycles with an even number of vertices is presented. This algorithm is used to determine the routing number for even cycles. Bounds on the routing number for several classes of graphs are determined. Finally, a new lower bound for any graph based upon diameter is considered.

You can download a PostScript [261 KB] or an Adobe Acrobat (PDF) [212 KB] version of the paper. The PDF version was generated from the PostScript version, so the PostScript version looks better if you can view it.

---

The Matching Model for Routing Permutations on Graphs Copyright © 1997 Rodney Waldhoff. All Rights Reserved. My root page: http://i.am/rwald Rod Waldhoff · mailto:rwald@hotmail.com · http://i.am/rwald