Unpaired Many-to-Many Disjoint Path Covers in Nonbipartite Torus-Like Graphs With Faulty Elements

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, S = {s(1), ... , s(k)} and T = {t(1), ... , t(k)}, in graph G, an unpaired many-to-many k-disjoint path cover joining S and T is a disjoint path cover {P-1, ... , P-k}, in which each path P-i runs from source s(i) to some sink t(j). 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 m-dimensional nonbipartite torus, m >= 2, with at most f vertex and/or edge faults has an unpaired many-to-many k-disjoint path cover joining arbitrary disjoint sets S and T of size k each, subject to k >= 1 and f + k <= 2m - 2. The bound of 2m - 2 on f + k is nearly optimal.

Automated summary

This paper discusses the problem of finding disjoint paths in the underlying graph of an interconnection network in parallel processing. It reveals that constructing a nonbipartite torus-like graph with good disjoint-path-cover properties from lower dimensional torus-like graphs can retain the good property. Consequently, nonbipartite tori with at most f vertex and/or edge faults can have unpaired many-to-many disjoint path covers joining arbitrary disjoint sets.