### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993 |

Publisher | Association for Computing Machinery |

Pages | 583-591 |

Number of pages | 9 |

ISBN (Electronic) | 0897915917 |

DOIs | |

State | Published - Jun 1 1993 |

Externally published | Yes |

Event | 25th Annual ACM Symposium on Theory of Computing, STOC 1993 - San Diego, United States Duration: May 16 1993 → May 18 1993 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | Part F129585 |

ISSN (Print) | 0737-8017 |

### Other

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

Country | United States |

City | San Diego |

Period | 5/16/93 → 5/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

*Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993*(pp. 583-591). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129585). Association for Computing Machinery. https://doi.org/10.1145/167088.167239