Multicolor routing in the undirected hypercube

Multicolor routing in the undirected hypercube

0.00 Avg rating0 Votes
Article ID: iaor20013558
Country: Netherlands
Volume: 100
Issue: 3
Start Page Number: 169
End Page Number: 181
Publication Date: Mar 2000
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: communication
Abstract:

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 Qn denote the n-dimensional hypercube, for arbitrary n≥1. We show that a routing problem (Qn,R) 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. Since, for any positive d, there is a multigraph R of degree d such that any solution (Qn,R) 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.

Reviews

Required fields are marked *. Your email address will not be published.