Abstract
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 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.
Back to my main page.
Back to the matching model index.
Back to my portfolio.
Back to my resume.