Constructing Optimal Subnetworks for the Crossed Cube Network

We present an algorithm that constructs subnetworks from an n-dimensional crossed cube, denoted CQ n, so that for any given κ, 2 ≤ κ ≤ n - 1, the algorithm can generate a κ-connected subnetwork that contains all 2 n original nodes of CQ n and preserves the symmetrical structure. The κ-connected subnetworks constructed are all optimal in the sense that they use the minimum number of links to maintain the required connectivity. Being able to construct κ-connected, all-node subnetworks are important in many applications, such as computing in the presence of faulty links, or diagnosing the system with a lower fault bound. Links that are not used by the induced subnetworks could be used in parallel by some other computing tasks, improving the overall resource utilization of the system