Constructing optimal subnetworks for the crossed cube network

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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.

Original languageEnglish
Pages (from-to)86-93
Number of pages8
Issue number2
StatePublished - Sep 2012


  • connectivity
  • crossed cube
  • induced subgraph
  • interconnection architectures
  • network topology

Cite this