Multicolor Routing in the Undirected Hypercube

Qian-Ping Gu$^*$ and Hisao Tamaki$^{**}$
\vskip 0.2in

$*$The University of Aizu
Aizu-Wakamatsu,
Fukushima, 965-8580 Japan
Email: qian@u-aizu.ac.jp

$**$Department of Computer Science,
Meiji University
1-1-1 Higashimita, Tamaku, Kawasaki, 214 Japan
E-mail: tamaki@cs.meiji.ac.jp


Abstract:
An {\em 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 {\em 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 $Q_n$ denote the $n$-dimensional hypercube, for arbitrary $n \geq 1$.
We show that a routing problem $(Q_n, R)$ always admits a $4d$-colorable
solution where $d$ is the maximum vertex degree of $R$.
%The previous bound is 16-colors for $d\leq 2$
%given by Aumann and Rabani [SODA95, pages 567-576].
%Our result improves over the previous one by a factor
%of two for $d=2$ and of four for $d=1$.
This improves over the $16\lceil d/2\rceil $-color
result which is implicit in the
previous work of Aumann and Rabani [SODA95, pages 567-576].
Since, for any positive $d$, there is a multigraph $R$ of degree $d$ such that
any solution to $(Q_n, 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.

Key words: multicolor routing,
        edge-disjoint paths,
        algorithm, circuit-switched network