Cube-connected cycles

Cube-connected cycles
The cube-connected cycles of order 3, arranged geometrically on the vertices of a truncated cube.

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 Preparata & Vuillemin (1981) for use as a network topology in parallel computing.

Contents

Definition

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.

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. Because it is a Cayley graph, it is vertex-transitive: there is a symmetry of the graph mapping any vertex to any other vertex.

The diameter of the cube-connected cycles of order n is 2n + ⌊n/2⌋ − 2 for any n ≥ 4; the farthest point from (xy) is (2n − x − 1, (y + n/2) mod n) (Friš, Havel & Liebl 1997). Sýkora & Vrťo (1993) showed that the crossing number of CCCn is ((1/20) + o(1)) 4n.

According to the Lovász conjecture, the cube-connected cycle graph should always contain a Hamiltonian cycle, and this is now known to be true. More generally, although these graphs are not pancyclic, they contain cycles of all but a finite number of possible even lengths, and when n is odd they also contain many of the possible odd lengths of cycles (Germa, Heydemann & Sotteau 1998).

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 × time2 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 .
  • Germa, Anne; Heydemann, Marie-Claude; Sotteau, Dominique (1998), "Cycles in the cube-connected cycles graph", Discrete Applied Mathematics 83 (1-3): 135–155, doi:10.1016/S0166-218X(98)80001-2, MR1622968 .
  • 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 .

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Truncated cube — The truncated cube, or truncated hexahedron, is an Archimedean solid. It has 6 regular octagonal faces, 8 regular triangular faces, 24 vertices and 36 edges. Area and volume The area A and the volume V of a truncated cube of edge length a are::A …   Wikipedia

  • Hypercube graph — The hypercube graph Q4 Vertices 2n Edges 2n−1n …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Franco P. Preparata — (born December 1935) is a computer scientist, the An Wang Professor of Computer Science at Brown University. He is best known for his 1985 computational geometry book with Michael Shamos, for many years the standard textbook in the field, but… …   Wikipedia

  • Network topology — Diagram of different network topologies. Network topology is the layout pattern of interconnections of the various elements (links, nodes, etc.) of a computer[1][2] …   Wikipedia

  • Cayley graph — In mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph that encodes the structure of a discrete group. Its definition is suggested by Cayley s theorem (named after Arthur Cayley) and uses a particular, usually… …   Wikipedia

  • Omega network — An Omega network is a network configuration often used in parallel computing architectures. It is an indirect topology that relies on the perfect shuffle interconnection algorithm. Omega network with 8 processing elements Contents …   Wikipedia

  • CCC — may refer to: NOTOC Businesses and organizations* Consolidated Contractors Company, a large Middle Eastern and International EPC Contractor * Canterbury of New Zealand, a New Zealand based sports apparel company * Center for community change, one …   Wikipedia

  • CCC — com. abbr. Convert Character Code comp. abbr. Central Computational Computer comp. abbr. Central Computer Complex comp. abbr. Computer Control Complex dairy abbr. Chlorochline Chloride train. abbr. Civilian Conservation Corps abbr. Chaos Computer …   United dictionary of abbreviations and acronyms

  • Induced path — An induced path of length four in a cube. Finding the longest induced path in a hypercube is known as the snake in the box problem. In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”