TY - GEN

T1 - Routing permutations on graphs via matchings (extended abstract)

AU - Alon, N.

AU - Chung, F. R.K.

AU - Graham, R. L.

N1 - Publisher Copyright:
© 1993 ACM.

PY - 1993/6/1

Y1 - 1993/6/1

N2 - We consider a class of routing problems on connected graphs G. Initially, each vertex v of G is occupied by a "pebble" which has a unique destination in G, so that tt is a permutation of the vertices of G. It is required to route all the pebbles to their respective destinations by performing a sequence of moves of the following type: A disjoint set of edges is selected and the pebbles at each edge's endpoints are interchanged. The problem of interest is to minimize the number of steps required for any possible permutation x. The odd-even sorting network shows that in the very special case that G is an n-vertex path, any permutation can be routed in n steps. Here we investigate this routing problem for a variety of graphs G, including trees, complete graphs, hypercubes, Cartesian products of graphs, expander graphs and various Cayley graphs. In addition, we relate this routing problem to certain network flow problems, and to several graph invariants including diameter, eigenvalues and expansion coefficients. Three of our results are the following: (i) Any permutation can be routed on any n-vertex connected graph in less than 3n steps. For any regular graph on n vertices in which the absolute value of any nontrivial eigenvlaue is at most A, any permutation can be routed in 0{d2 log2 n/(d -A)2) steps. For any Cayley graph of a group of n elements with respect to a polylogarithmic (in n) number of generators, any permutation can be routed in a polylogarithmic number of steps if and only if the diameter of the graph is polylogarithmic.

AB - We consider a class of routing problems on connected graphs G. Initially, each vertex v of G is occupied by a "pebble" which has a unique destination in G, so that tt is a permutation of the vertices of G. It is required to route all the pebbles to their respective destinations by performing a sequence of moves of the following type: A disjoint set of edges is selected and the pebbles at each edge's endpoints are interchanged. The problem of interest is to minimize the number of steps required for any possible permutation x. The odd-even sorting network shows that in the very special case that G is an n-vertex path, any permutation can be routed in n steps. Here we investigate this routing problem for a variety of graphs G, including trees, complete graphs, hypercubes, Cartesian products of graphs, expander graphs and various Cayley graphs. In addition, we relate this routing problem to certain network flow problems, and to several graph invariants including diameter, eigenvalues and expansion coefficients. Three of our results are the following: (i) Any permutation can be routed on any n-vertex connected graph in less than 3n steps. For any regular graph on n vertices in which the absolute value of any nontrivial eigenvlaue is at most A, any permutation can be routed in 0{d2 log2 n/(d -A)2) steps. For any Cayley graph of a group of n elements with respect to a polylogarithmic (in n) number of generators, any permutation can be routed in a polylogarithmic number of steps if and only if the diameter of the graph is polylogarithmic.

UR - http://www.scopus.com/inward/record.url?scp=0027274223&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027274223&partnerID=8YFLogxK

U2 - 10.1145/167088.167239

DO - 10.1145/167088.167239

M3 - Conference contribution

AN - SCOPUS:0027274223

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 583

EP - 591

BT - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993

PB - Association for Computing Machinery

T2 - 25th Annual ACM Symposium on Theory of Computing, STOC 1993

Y2 - 16 May 1993 through 18 May 1993

ER -