Unpaired Many-to-Many Disjoint Path Covers in Nonbipartite Torus-Like Graphs With Faulty Elements
Jung-Heum Park · IEEE Access · 2022
One of the key problems in parallel processing is finding disjoint paths in the underlying graph of an interconnection network. Thedisjoint path coverof 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= {s1,...,sk} andT= {t1,...,tk}, in graphG, anunpaired many-to-many k-disjoint path coverjoiningSandTis a disjoint path cover {P1,...,Pk}, in which each pathPiruns from sourcesito some sinktj. 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, anm-dimensional nonbipartite torus,m≥ 2, with at mostfvertex and/or edge faults has an unpaired many-to-manyk-disjoint path cover joining arbitrary disjoint setsSandTof sizekeach, subject tok≥ 2 andf+k≤ 2m– 2. The bound of 2m– 2 onf+kis nearly optimal.