Constructing optimal subnetworks for the crossed cube network
Dajin Wang · Networks · 2011
Abstract We present an algorithm that constructs subnetworks from an n‐dimensional crossed cube, denoted CQn, so that for any given κ, 2 ≤ κ ≤ n − 1, the algorithm can generate a κ‐connected subnetwork that contains all 2n original nodes of CQn 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. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012