Embedding ofk-ary Complete Trees into Hypercubes with Uniform Load

The main result of this paper is an algorithm for embeddingk-ary complete trees into hypercubes with uniform load and asymptotically optimal dilation. The algorithm is fully scalable—the dimension of the hypercube can be chosen independent of the arity and height of the tree. The embedding enables to emulate optimally both Divide&Conquer computations onk-ary complete trees where only one level of nodes is active at a time and general computations based onk-ary complete trees where all tree nodes are active simultaneously. As a special case, we get an algorithm for embedding thek-ary complete tree of given height into its optimal hypercube with load 1 and asymptotically optimal dilation.     

On Embedding Binary Trees into Hypercubes

Hypercubes are known to be able to simulate other structures such as grids and binary trees. It has been shown that an arbitrary binary tree can be embedded into a hypercube with constant expansion and constant dilation. This paper presents a simple linear-time heuristic which embeds an arbitrary binary tree into a hypercube with expansion 1 and average dilation no more than 2. We also give some results extending good embeddings for parity-balanced binary trees to arbitrary binary trees. In particular, we show that a conjecture of I. Havel (Časopis Pěest. Mat.109 (1984), 135-152) implies embeddings of binary trees into hypercubes with expansion 1 and either dilation 2 or average dilation approaching 1, and embeddings with expansion 2 and dilation 1.     

Embedding Large Complete Binary Trees in Hypercubes with Load Balancing

This paper presents two methods for embedding arbitrarily large complete binary trees in fixed size hypercubes. The ability to embed arbitrarily large graphs in smaller graphs has important applications in massively parallel computing. The presented embedding methods are optimized mainly for balancing the processor loads, while minimizing dilation and congestion as far as possible.     

Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes

It is folklore that the double-rooted complete binary tree is a spanning tree of the hypercube of the same size. Unfortunately, the usual construction of an embedding of a double-rooted complete binary tree into a hypercube does not provide any hint on how this embedding can be extended if each leaf spawns two new leaves. In this paper, we present simple dynamic embeddings of double-rooted complete binary trees into hypercubes which do not suffer from this disadvantage. We also present edge-disjoint embeddings with optimal load and unit dilation. Furthermore, all these embeddings can be efficiently implemented on the hypercube itself such that the embedding of each new level of leaves can be computed in constant time. Because of the similarity, our results can be immediately transfered to complete binary trees.     

Embedding Complete Binary Trees into Star and Pancake Graphs

Let G and H be two simple undirected graphs. An embedding of the graph G into the graph H is an injective mapping f from the vertices of G to the vertices of H . The dilation of the embedding is the maximum distance between f(u),f(v) taken over all edges (u,v) of G . We give a construction of embeddings of dilation 1 of complete binary trees into star graphs. The height of the trees embedded with dilation 1 into the n -dimensional star graph is Ω (n log n) , which is asymptotically optimal. Constructions of embeddings of complete binary trees of dilation 2δ and 2δ +1 , δ≥ 1, into star graphs are given. The use of larger dilation allows embeddings of trees of greater height into star graphs. It is shown that all these constructions can be modified to yield embeddings of dilation 1 and 2δ , δ≥ 1 , of complete binary trees into pancake graphs. Received February 1996, and in final form October 1997.     

Embedding of Binomial Trees in Hypercubes with Link Faults

We study the embedding of binomial trees with variable roots inn-dimensional hypercubes (n-cubes) with faulty links. A simple embedding algorithm is first proposed that can embed ann-level binomial tree in ann-cube with up ton−1 faulty links in log(n−1) steps. We then extend the result to show that spanning binomial trees exist in a connectedn-cube with up to ⌈(3(n−1)/2)⌉−1 faulty links. A constructive proof is provided to locate spanning binomial trees in the given system. Our results reveal the fault tolerance property of hypercubes and they can be used to predict the performance of broadcasting and reduction operations, where the binomial tree structure is commonly used.     

Embedding Hamiltonian Cycles into Folded Hypercubes with Faulty Links

It has been known that an n-dimensional hypercube (n-cube for short) can always embed a Hamiltonian cycle when the n-cube has no more than n−2 faulty links. In this paper, we study the link-fault tolerant embedding of a Hamiltonian cycle into the folded hypercube, which is a variant of the hypercube, obtained by adding a link to every pair of nodes with complementary addresses. We will show that a folded n-cube can tolerate up to n−1 faulty links when embedding a Hamiltonian cycle. We present an algorithm, FT_HAMIL, that finds a Hamiltonian cycle while avoiding any set of faulty links F provided that |F|⩽n−1. An operation, called bit-flip, on links of hyper-cube is introduced. Simple yet elegant, bit-flip will be employed by FT_HAMIL as a basic operation to generate a new Hamiltonian cycle from an old one (that contains faulty links). It is worth pointing out that the algorithm is optimal in the sense that for a folded n-cube, n−1 is the maximum number for |F| that can be tolerated, F being an arbitrary set of faulty links.     

Embedding Hypercubes and Related Networks into Mesh-Connected Processor Arrays

In this paper we study the problem of how computations programmed for hypercubes, and their bounded-degree relatives, the shuffle-exchange and cube-connected-cycles, can be efficiently emulated by mesh-connected arrays of processing elements. The emulations we present are implemented via graph embeddings. The graph embeddings we present are all optimal with respect to congestion, and are also noteworthy for they yield efficient emulation programs that are written in a SIMD style without the use of indirect addressing. The paper includes the three following emulation results, where each emulation algorithm requires no indirection. For any n ≥ 1 and fixed r ≥ 1, an n-sided r-dimensional mesh can emulate an n2ⁿ-node cube-connected-cycles network with slowdown Θ(2ⁿ/n^r−1), a 2ⁿ-node shuffle-exchange network with slowdown Θ(2ⁿ/n^r), and a 2ⁿ-node hypercube network operating in a weak model, with slowdown Θ(2ⁿ log n/n^r).     

Dilation-5 Embedding of 3-Dimensional Grids into Hypercubes

We present an algorithm to map the nodes of a 3-dimensional grid to the nodes of its optimal hypercube on a one-to-one basis with dilation at most 5.     

Embedding All Binary Trees in the Hypercube

An O(N²) heuristic algorithm is presented that embeds all binary trees, with dilation 2 and small average dilation, into the optimal-sized hypercube. The heuristic relies on a conjecture about all binary trees containing a perfect matching. It provides a practical and robust technique for mapping binary trees into the hypercube and ensures that the communication load is evenly distributed across the network assuming any shortest path routing strategy. One contribution of this work is the identification of a rich collection of binary trees that can be easily mapped into the hypercube.     

Embedding the Complete Tree in the Hypercube

Let H_n be the n-dimensional boolean hypercube with 2ⁿ vertices labeled {0, 1, ... 2ⁿ − 1}, with an edge between two vertices whenever their Hamning distance is 1. We describe a spanning tree T_n of H_n with the following properties. T_n is complete for the first n − 2 levels with the remaining nodes on level n and n − 1 of the tree. Except for levels n and n − 1, there is a dilation 2 embedding of H_k on level k of T_n. T_n has minimum internal path length with respect to all binary spanning trees of H_n. Finally, each subtree of T_n is contained in the optimal sized subcube of H_n. This collection of almost complete binary trees is important for the implementation of tree-structured computation on hypercube configured multiprocessors.     

Embeddings of Hypercubes and Grids into de Bruijn Graphs

An embedding of a graph G into a graph H is an injective mapping f from the vertices of G into the vertices of H together with a mapping P_f of edges of G into paths in H. The dilation of the embedding is tile maximum taken over all the lengths of the paths P_f(xy) associated with the edges xy of G. We show that it is possible to embed a D-dimensional hypercube into the binary de Bruijn graph of the same order and diameter with dilation at most [D/2]. Similarly a majority of planar grids can be embedded into a binary de Bruijn graph of the same or nearly the same order with dilation at most [D/2] where D is the diameter of the de Bruijn graph.     

Embedding meshes into twisted-cubes

The n-dimensional twisted-cube, TN_n, is a variation of the hypercube. In this paper, we study embedding of meshes into TN_n. We prove three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded into TN_n with dilation 1 and expansion 1. (2) For any integer n ? 4, an m × k(m ? 3, k ? 3) mesh cannot be embedded into TN_n with dilation 1. (3) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded into TN_n with dilation 2 and expansion 1.     

One-to-Many Embeddings of Hypercubes into Cayley Graphs Generated by Reversals

Among Cayley graphs on the symmetric group, some that have a noticeably low diameter relative to the degree of regularity are examples such as the ``star' network and the ``pancake' network, the latter a representative of a variety of Cayley graphs generated by reversals. These diameter and degree conditions make these graphs potential candidates for parallel computation networks. Thus it is natural to investigate how well they can simulate other standard parallel networks, in particular hypercubes. For this purpose, constructions have previously been given for low dilation embeddings of hypercubes into star networks. Developing this theme further, in this paper we construct especially low dilation maps (e.g., with dilation 1, 2, 3, or 4) of hypercubes into pancake networks and related Cayley graphs generated by reversals. Whereas obtaining such results by the use of ``traditional' graph embeddings (i.e., one-to-one or many-to-one embeddings) is sometimes difficult or impossible, we achieve many of these results by using a nontraditional simulation technique known as a ``one-to-many' graph embedding. That is, in such embeddings we allow each vertex in the guest (i.e., domain) graph to be associated with some nonempty subset of the vertex set of the host (i.e., range) graph, these subsets satisfying certain distance and connection requirements which make the simulation possible. Received July 30, 1997, and in revised form July 18, 2001. Online publication October 30, 2001.     

Embedding meshes into crossed cubes

Crossed cubes are important variants of hypercubes. In this paper, we consider embeddings of meshes in crossed cubes. The major research findings in this paper are: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in the n-dimensional crossed cube with dilation 1 and expansion 2. The obtained results are optimal in the sense that the dilations of the embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion because it has the smallest expansion 1.     

Embedding of tree networks into hypercubes

The hypercube is a good host graph for the embedding of networks of processors because of its low degree and low diameter. Graphs such as trees and arrays can be embedded into a hypercube with small dilation and expansion costs, but there are classes of graphs which can be embedded into a hypercube only with large expansion cost or large dilation cost.     

Embedding meshes into locally twisted cubes

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQ_n(V, E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in LTQ_n with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in LTQ_n with dilation 1 and expansion 2. (3) For any integer n ? 3, a 4  × (2ⁿ⁻² − 1) mesh can be embedded in LTQ_n with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion. We also present the analysis of 2p × 2q mesh embedding in locally twisted cubes.     

Embedding Information Security into the Organization

Risk and business have always been inseparable, but new information security risks pose unknown challenges. How should firms organize and manage to improve enterprise security? Here, the authors describe how chief information security officer (CISOs) are working to build secure organizations.