Cube-connected cycles

It was introduced by Preparata & Vuillemin (1981) for use as a network topology in parallel computing.

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

The diameter of the cube-connected cycles of order n is 2n + ⌊n/2⌋ − 2 for any n ≥ 4; the farthest point from (x, y) is (2n − x − 1, (y + n/2) mod n).

[3] 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.

Preparata and Vuillemin showed that a planar layout based on this network has optimal area × time2 complexity for many parallel processing tasks.