کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437422 | 690139 | 2016 | 11 صفحه PDF | دانلود رایگان |
Given two disjoint vertex-sets, S={s1,…,sk}S={s1,…,sk} and T={t1,…,tk}T={t1,…,tk} in a graph, a paired many-to-many k-disjoint path cover between S and T is a set of pairwise vertex-disjoint paths {P1,…,Pk}{P1,…,Pk} that altogether cover every vertex of the graph, in which each path PiPi runs from sisi to titi. A family of hypercube-like interconnection networks, called restricted hypercube-like graphs , includes most non-bipartite hypercube-like networks found in the literature, such as twisted cubes, crossed cubes, Möbius cubes, recursive circulant G(2m,4)G(2m,4) of odd m, etc. In this paper, we show that every m -dimensional restricted hypercube-like graph, m≥5m≥5, with at most f vertex and/or edge faults being removed has a paired many-to-many k-disjoint path cover between arbitrary disjoint sets S and T of size k each, subject to k≥2k≥2 and f+2k≤m+1f+2k≤m+1. The bound m+1m+1 on f+2kf+2k is the best possible.
Journal: Theoretical Computer Science - Volume 634, 27 June 2016, Pages 24–34