Cube-connected cycles

In graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by by Preparata & Vuillemin (1981) for use as a network topology in parallel computing.

Definition

The cube-connected cycles of order n (denoted CCC_n) can be defined as a graph formed from a set of n2ⁿ nodes, indexed by pairs of numbers (x, y) where 0 ≤ x < 2ⁿ and 0 ≤ y < n. Each such node is connected to three neighbors: (x, (y + 1) mod n), (x, (y − 1) mod n), and (x ⊕ 2^y, y) where "⊕" denotes the bitwise exclusive or operation on binary numbers.

Properties

The cube-connected cycles of order n is the Cayley graph of a group that acts on binary words of length n by rotation and flipping bits of the word (Akers & Krishnamurthy 1989; Annexstein, Baumslag & Rosenberg 1990). The generators used to form this Cayley graph from the group are the group elements that act by rotating the word one position left, rotating it one position right, or flipping its first bit. The diameter of the cube-connected cycles of order n is <math>\scriptstyle 2n\, +\, \lfloor n/2\rfloor \,-\, 2</math>; the farthest point from (x, y) is (2ⁿ − x − 1, (y + n/2) mod n) (Friš, Havel & Liebl 1997). Sýkora & Vrťo (1993) showed that the crossing number of CCC_n is (1 + o(1))4ⁿ/20.

Parallel processing application

Cube-connected cycles were investigated by Preparata & Vuillemin (1981), who applied these graphs as the interconnection pattern of a network connecting the processors in a parallel computer. In this application, cube-connected cycles have the connectivity advantages of hypercubes while only requiring three connections per processor. Preparata and Vuillemin showed that a planar layout based on this network has optimal area × time² complexity for many parallel processing tasks.

References

• Akers, Sheldon B. & Krishnamurthy, Balakrishnan (1989), "A group-theoretic model for symmetric interconnection networks", IEEE Transactions on Computers 38 (4): 555–566, DOI 10.1109/12.21148.
• Annexstein, Fred; Baumslag, Marc & Rosenberg, Arnold L. (1990), "Group action graphs and parallel architectures", SIAM Journal on Computing 19 (3): 544–569, DOI 10.1137/0219037.
• Friš, Ivan; Havel, Ivan & Liebl, Petr (1997), "The diameter of the cube-connected cycles", Information Processing Letters 61 (3): 157–160, DOI 10.1016/S0020-0190(97)00013-6.
• Preparata, Franco P. & Vuillemin, Jean (1981), "The cube-connected cycles: a versatile network for parallel computation", Communications of the ACM 24 (5): 300–309, DOI 10.1145/358645.358660.
• Sýkora, Ondrej & Vrťo, Imrich (1993), "On crossing numbers of hypercubes and cube connected cycles", BIT Numerical Mathematics 33 (2): 232–237, DOI 10.1007/BF01989746.