Multicolor routing in the undirected hypercube
An undirected routing problem is a pair (G,R) where G is an undirected graph and R is an undirected multigraph such that V(G)=V(R) . A solution to an undirected routing problem (G,R) is a collection P of undirected paths of G (possibly containing multiple occurrences of the same path) such that edges of R are in one-to-one correspondence with the paths of P , with the path corresponding to edge {u,v} connecting u and v . We say that a collection of paths P is k -colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let denote the n -dimensional hypercube, for arbitrary n?1 . We show that a routing problem always admits a 4d -colorable solution where d is the maximum vertex degree of R . This improves over the 16?d/2? -color result which is implicit in the previous work of Aumann and Rabani [SODA95, pp. 567576]. Since, for any positive d , there is a multigraph R of degree d such that any solution to requires at least d colors, our result is tight up to a factor of four. In fact, when d=1 , it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors.
multicolor routing edge-disjoint paths algorithm circuit-switched network