Multicolor routing in the undirected hypercube |
| |
Authors: | Qian-Ping Gu Hisao Tamaki |
| |
Institution: | a Foundation of Computer Science Lab, The University of Aizu, Aizu-Wakamatsu, Fukushima, 965-8580 Japan b Department of Computer Science, Meiji University 1-1-1 Higashimita, Tamaku, Kawasaki, 214 Japan |
| |
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 n1. 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 16d/2-color result which is implicit in the previous work of Aumann and Rabani SODA95, pp. 567–576]. Since, for any positive d, there is a multigraph R of degree d such that any solution to (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. |
| |
Keywords: | Multicolor routing Edge-disjoint paths Algorithm Circuit-switched network |
本文献已被 ScienceDirect 等数据库收录! |
|