Originator(s): N. Alon, F.R.K. Chung, R.L. Graham (presented by West - REGS 2008)
Definitions: Given a permutation π of the vertices of a connected graph G, the routing problem is the problem of simultaneously moving a pebble from each vertex v to its destination π(v). A step of the routing procedure specifies a matching in G and on each edge of the matching exchanges the pebbles. The routing number rt(G) is the maximum, over all permutations, of the number of steps needed to move each pebble to its destination.
Background: The pebbles represent packets of information. Each packet has a destination address. Restricting the setting to permutations is a reasonable simplification to study the length of time needed for distributed communication on various graphs. Among connected graphs, trees have the highest routing numbers, since extra edges only provide more flexibility for routing, so it is natural to seek the maximum of rt(G) over n-vertex trees. For applications to routing networks, it is also natural to study rt(G) on expander graphs.
Conjecture 1: The largest value of the routing number on n-vertex trees is ⌊3(n-1)/2⌋, achieved only by the star with n-1 edges.
Comments: It is not hard to show that the star achieves equality (observed by Goddard). Zhang [Z] proved Conjecture 1 asymptotically, proving (by specifying a switching procedure) that rt(G)≤(3/2)n+9log3n when G is a tree. (Earlier bounds were 3n in [ACG], 13n/5 in [RSZ], 2n by both [HL] and Goddard.)
[ACG] provides several easy lower bounds of interest:
rt(G)≥diam(G),
rt(G)≥D/(2α'(G)),
where D=∑Gd(v,π(v)) and α'(G) is the
maximum size of a matching, and
rt(G)&ge 2t/|S|,
where S is a separating set and t
is the minimum order of components of G-S.
Similarly, rt(G)&ge 2t/[S,¯S]|-1, where [S,¯S] is an edge cut and t=min{|S|,|¯S|}. This yields rt(Pn)&ge n (for even n), and in fact equality holds (for all n). [ACR] remarked that any permutation on Pn can be sorted in n steps using only exchanges on odd-indexed edges on odd steps and even-indexed edges on even steps.
Question 2: Which graphs have routing number 2?
Comment: [ACG] showed that rt(Kn)=2. It suffices to show that a single cycle can be routed in one step. To achieve (m,m-1,...,1), first apply the matching that switches all pairs of the form (i,m+1-i), and then all of the form (j,m-j). Goddard proved that rt(Kn,n)=4; more generally, if m≤n, then rt(Km,n)≤2⌈n/m⌉+2.
Conjecture 3: For the d-dimensional hypercube, rt(Qd)=d+1.
Comment: For cartesian product in general, [BA] proved that rt(G×H)≤2rt(G)+rt(H) (the basic idea is to route on copies of G, then copies of H, then copies of G). This yields rt(Qd)≤2d-1 and rt(Pm×Pn)&le 2m+n when m≤n, but the optimal values are not known. Indeed, it is not known whether always rt(G×G)≥rt(G).
See [ACG] for further questions about routing number of expander graphs and other topics.
References:
[ACG] N. Alon, F. R. K. Chung, and R. L. Graham, Routing permutations on
graphs via matchings, SIAM J. Discrete Math., 7 (1994), pp. 516--530.
[BA] Baumslag, Marc; Annexstein, Fred A; unified framework for off-line
permutation routing in parallel networks. Parallel algorithms and architectures
(Crete, 1990). Math. Systems Theory 24 (1991), no. 4, 233--251.
[HL] P. Hoyer and K. Larson; Permutation Routing via Matchings, Tech. report
96--16, Institut for Matematik og Datalogi, Odense Universitet, Denmark, 1996
[RSZ] A. Roberts, A. Symvonis, and L. Zhang; Routing on trees via matchings, in
Proc. 4th Workshop on Algorithms and Data Structures, Kingston, Ontario, Canada,
1995, Lecture Notes in Comput. Sci. 955, Springer-Verlag, New York, pp.
251--263.
[Z] Zhang, Louxin; Optimal bounds for matching routing on trees. SIAM J. Discrete
Math. 12 (1999), no. 1, 64--77 (electronic).