论文标题
通过匹配在光谱扩展器上的路由排列
Routing permutations on spectral expanders via matchings
论文作者
论文摘要
我们考虑以下基于匹配的路由问题。最初，连接图$ g $的每个顶点$ v $被鹅卵石占据，该卵石具有唯一的目的地$π（v）$。在每一轮比赛中，缝制$ g $中选定的匹配边缘的鹅卵石被换成，目标是将每个卵石伸入其目标顶点，以尽可能少的回合。我们表明，如果$ g $是一个足够强的$ d $ groumbard频谱扩展器，那么在$ o（\ log n）$ rounds中可以实现任何排列$π$。这对于常数$ d $是最佳选择，并解决了Alon，Chung和Graham的问题[Siam J. Incret Math。，7（1994），第516---530页]。
We consider the following matching-based routing problem. Initially, each vertex $v$ of a connected graph $G$ is occupied by a pebble which has a unique destination $π(v)$. In each round the pebbles across the edges of a selected matching in $G$ are swapped, and the goal is to route each pebble to its destination vertex in as few rounds as possible. We show that if $G$ is a sufficiently strong $d$-regular spectral expander then any permutation $π$ can be achieved in $O(\log n)$ rounds. This is optimal for constant $d$ and resolves a problem of Alon, Chung, and Graham [SIAM J. Discrete Math., 7 (1994), pp. 516--530].
