Routing permutations on graphs via matchings (extended abstract)

N. Alon, F. R.K. Chung, R. L. Graham

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993
PublisherAssociation for Computing Machinery
Pages583-591
Number of pages9
ISBN (Electronic)0897915917
DOIs
StatePublished - Jun 1 1993
Event25th Annual ACM Symposium on Theory of Computing, STOC 1993 - San Diego, United States
Duration: May 16 1993May 18 1993

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129585
ISSN (Print)0737-8017

Other

Other25th Annual ACM Symposium on Theory of Computing, STOC 1993
CountryUnited States
CitySan Diego
Period5/16/935/18/93

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Routing permutations on graphs via matchings (extended abstract)'. Together they form a unique fingerprint.

Cite this