| Summary: | One of the key problems in parallel processing is finding disjoint paths in the underlying graph of an interconnection network. The disjoint path cover of a graph is a set of pairwise vertex-disjoint paths that altogether cover every vertex of the graph. Given disjoint source and sink sets, <inline-formula> <tex-math notation="LaTeX">$S = \{ s_{1},\ldots,s_{k}\}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$T = \{t_{1},\ldots, t_{k}\}$ </tex-math></inline-formula>, in graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>, an unpaired many-to-many <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-disjoint path cover joining <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> is a disjoint path cover <inline-formula> <tex-math notation="LaTeX">$\{ P_{1}, \ldots, P_{k}\}$ </tex-math></inline-formula>, in which each path <inline-formula> <tex-math notation="LaTeX">$P_{i}$ </tex-math></inline-formula> runs from source <inline-formula> <tex-math notation="LaTeX">$s_{i}$ </tex-math></inline-formula> to some sink <inline-formula> <tex-math notation="LaTeX">$t_{j}$ </tex-math></inline-formula>. In this paper, we reveal that a nonbipartite torus-like graph, if built from lower dimensional torus-like graphs that have good disjoint-path-cover properties of the unpaired type, retains such a good property. As a result, an <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula>-dimensional nonbipartite torus, <inline-formula> <tex-math notation="LaTeX">$m \geq 2$ </tex-math></inline-formula>, with at most <inline-formula> <tex-math notation="LaTeX">$f$ </tex-math></inline-formula> vertex and/or edge faults has an unpaired many-to-many <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-disjoint path cover joining arbitrary disjoint sets <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> of size <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> each, subject to <inline-formula> <tex-math notation="LaTeX">$k \geq 1$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$f+k \leq 2m-2$ </tex-math></inline-formula>. The bound of <inline-formula> <tex-math notation="LaTeX">$2m-2$ </tex-math></inline-formula> on <inline-formula> <tex-math notation="LaTeX">$f+k$ </tex-math></inline-formula> is nearly optimal.
|
|---|