2022/09/08 by Rajko Nenadov, Nenadov, Rajko · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2209.03838
openalex publication_date 2022/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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].