Routing permutations on graphs via matchings
Routing permutations on graphs via matchings
复制标题
通过匹配在图上进行路由排列
DOI：
10.1145/167088.167239
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
R. Graham
中科院分区：
文献类型：
--
作者：
N. Alon;F. C. Graham;R. Graham
研究了连通图G上的一类路由问题。最初，$G$的每个顶点$v$被一个在$G$中具有唯一目的地$\pi(V)$的‘pebble’占据(因此，$\pi$是$G$的顶点的排列)。需要通过执行以下类型的移动序列将所有鹅卵石传送到它们各自的目的地：选择一组不相交的边，并互换每条边的端点处的鹅卵石。感兴趣的问题是最小化任何可能的排列$\pi$所需的步骤数。
本文研究了树、完全图、超立方体、图的笛卡儿积、扩展图和Cayley图等多种图的路由问题。此外，此路由问题与某些网络流问题以及包括直径、特征值和扩展系数在内的几个图不变量有关。
A class of routing problems on connected graphs $G$ is considered. Initially, each vertex $v$ of $G$ is occupied by a ``pebble'' that has a unique destination $\pi (v)$ in $G$ (so that $\pi$ is a permutation of the vertices of $G$). It is required that all the pebbles be routed 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 $\pi$.
This paper investigates this routing problem for a variety of graphs $G$, including trees, complete graphs, hypercubes, Cartesian products of graphs, expander graphs, and Cayley graphs. In addition, this routing problem is related to certain network flow problems, and to several graph invariants including diameter, eigenvalues, and expansion coefficients.