Narrow Results

Graph embedding is the major technique which is used to map guest graph into host graph. In architecture simulation, graph embedding is said to be one of the strongest application for the execution of parallel algorithms and simulation of various interconnection networks. In the recent paper [1], Berin et al. proposed a novel approach for embedding an augmented hypercube into a tree-like networks and provided the minimum wirelength of the resulting embedding, and they mentioned that this problem is open for other guest networks. In this paper, we solve one of the open problems by considering folded hypercube as the guest network. Additionally, we discuss the implementation of rooted complete binary tree in Network On Chips. Our findings contribute to the optimization of VLSI layout and provide insights into the design of efficient network structures.

The series of Extended Fibonacci cubes defined in terms of Fibonacci strings are classes of incomplete hypercubes. The Wiener index of a network, also known as the transmission of a network, is the sum of distances between all pairs of vertices in the network. It provides the average distance between any two nodes of the network. An embedding of a graph $G$ into a graph $H$ is a one-to-one mapping of $G$ into $H$. Wirelength is a widely studied embedding parameter. In this paper, we determine the Wiener index of all cubes in the series of Extended Fibonacci cubes. We also find the wirelength of embedding a complete graph with a deleted edge onto the Extended Fibonacci cubes.

Solving R. J. Daverman’s problem, V. S. Krushkal described sticky Cantor sets in ${ℝ}^N$ for $N\ge 4$. Such sets cannot be isotoped off themselves by small ambient isotopies. Using Krushkal sets, we present a new series of wild embeddings related to a question of J. W. Cannon and S. G. Wayment (1970). Namely, for $N\ge 4$, we construct examples of compacta $X\subset {ℝ}^N$ with the following two properties: some sequence $\{X_i\subset {ℝ}^N\setminus X,i\in \mathbb{N}\}$ converges homeomorphically to $X$, but no uncountable family of pairwise disjoint sets $Y_{\alpha }\subset {ℝ}^N$ exists such that each $Y_{\alpha }$ is ambiently homeomorphic to $X$.

We consider the problem of finding Hamiltonian cycles, linear arrays and rings of a faulty supercube, if any. The proof of the existence of Hamiltonian cycles in hypercubes is easy due to the fact they are symmetric graphs. Since the supercube is asymmetric, the proof of the existence of Hamiltonian cycles is not trivial. We show that for any supercube S_N, where N is the number of nodes in the supercube, there exists a Hamiltonian cycle. This implies that for any r such that 3≤r≤N, there exists a cycle of r nodes in a supercube. There are embedding algorithms proposed in this paper. The embedding algorithms show a ring with any number of nodes which can be embedded in a faulty supercube with load 1, congestion 1 and dilation 4 such that O(n²-(⌊log₂ m⌋)²) faults can be tolerated, where n is the dimension of the supercube and m is the number of nodes of the ring.

In this paper we introduce a class of trees, called generalized compressed trees. Generalized compressed trees can be derived from complete binary trees by performing certain ‘contraction’ operations. A generalized compressed tree CT of height h has approximately 25% fewer nodes than a complete binary tree T of height h. We show that these trees have smaller (up to a 74% reduction) 2-dimensional and 3-dimensional VLSI layouts than the complete binary trees. We also show that algorithms initially designed for T can be simulated by CT with at most a constant slow-down. In particular, algorithms having non-pipelined computation structure and originally designed for T can be simulated by CT with no slow-down.

In numerical computations, the method of divided differences is a very important technique for polynomial approximations. Consider a pipelined divided–difference computation for approximating an nth degree polynomial. This paper first presents a method to transform the computational structure of divided differences into the pyramid tree with nodes. Based on graph embedding technique, without any extra communication delay, the pipelined divided–difference computation can be performed in a (2k + 1)-dimensional fault–free hypercube for n + 1 = 2^k + t, k > 0, and 0 < t < 2^k; the pipelined divided-difference computation can be further performed in a (2k + 2)-dimensional faulty hypercube to tolerate arbitrary (k - 1) faulty nodes/links. To the best of our knowledge, this is the first time such mapping methods are being proposed in the literature.

The Incrementally Extensible Hypercube (IEH) is a novel interconnection network derived from the hypercube. Unlike the hypercube, the IEH graph is incrementally extensible, that is, it can be constructed for any number of nodes. In addition, it has optimal fault tolerance and its diameter is logarithmic in the number of nodes and the difference of the maximum and the minimum degree of a node in the graph is (i.e., the graph is almost regular). In this paper, we show that almost the entire IEH graph, except for those with N =2ⁿ-1 nodes for all , has a Hamiltonian cycle; if an IEH graph has N=2ⁿ-1 nodes then it has only a Hamiltonian path, not cycle. These results enable us to obtain the good embedding of rings and linear arrays into the IEH graph.

Topology embedding enables one to execute a protocol designed for a specific (virtual) topology on another (real) topology by embedding the virtual topology on the real topology. In this paper, we propose a self-stabilizing emulation technique that provides reliable communication on a virtual topology in the presence of transient faults in real topology. The proposed protocol improves the execution slowdown of previous two protocols [19, 20] and provides adaptive message delivery delay on the emulated channels, which is a new type of adaptability against transient faults.

Generalized cubes are a subclass of hypercube-like networks that are employed by a number of parallel algorithms. Linear array is common topology of multicomputer system. So congestion is very useful to improve algorithm performance for implementing generalized cube communication pattern on linear array. This paper addresses the congestion of generalized cube communication patterns embedding into linear array topology. For this purpose, the maximum m-induced subgraph of generalized cube is determined firstly, which is very important for discussing the congestion. Then an embedding scheme is described, and the congestion is shown to attain the minimum, which guarantees the optimality of the proposed scheme.

The augmented cube $A{Q}_n$ is a variation of the hypercube $Q_n$. This paper considers the fault-tolerant Panconnectivity of $A{Q}_n$. Assume that $F\subseteq V(A{Q}_n)\cup E(A{Q}_n)$ and $n\ge 4$. We prove that for any two fault-free vertices $u$ and $v$ with distance $d$ in $A{Q}_n$, there exists a fault-free path $P_{uv}$ of each length from $max\{d+2,4\}$ to $2^n-f_v-1$ in $A{Q}_n-F$ if $\left|F\right|\le 2n-4$, where $f_v$ is the number of faulty vertices in $A{Q}_n$. Moreover, the bound is sharp.

The technique used in studying the computational capabilities of interconnection networks and task distribution is graph embedding. Based on the recursively constructed graphs, the hypercube network is popular for its structure. Many variants of hypercube are considered in the literature. Augmented cube is considered as one of the best variants of hypercube as it holds many desirable properties like optimal routing in linear time complexity, vertex symmetricity, wide diameter and maximum connectivity. Our work deals with the exact wirelength, when augmented cube is embedded into certain tree and windmill structures.

We propose a constant node degree network topology, multitriangle, which is hierarchical, recursive, and expansive. First we introduce a corner cutting approach that generates a set of new network topologies (including multitriangles), followed by a formal definition of the multitriangle network and discussion of its properties. The salient features of this network are that it is a constant node degree network and it can be viewed as a hierarchical ring, a popular topology which has been adopted in several commercial systems. Algorithms for node-to-node routing, hierarchical ring routing, optimal ring routing, and broadcasting are presented. The multitriangle network is analyzed in terms of diameter, degree, average distance, and message density, and results are compared with other relevant networks.

The problems of mapping and load balancing applications on arbitrary networks are considered. A novel diffusion algorithm is presented to solve the mapping problem. It complements the well known diffusion algorithms for load balancing which have enjoyed success on massively parallel computers (MPPs). Mapping is more difficult on interconnection networks than on MPPs because of the variations which occur in network topology. Popular mapping algorithms for MPPs which depend on recursive topologies are not applicable to irregular networks. The most celebrated of these MPP algorithms use information from the Laplacian matrix of a graph of communicating processes. The diffusion algorithm presented in this paper is also derived from this Laplacian matrix. The diffusion algorithm works on arbitrary network topologies and is dramatically faster than the celebrated MPP algorithms. It is delay and fault tolerant. Time to convergence depends on initial conditions and is insensitive to problem scale. This excellent scalability, among other features, makes the diffusion algorithm a viable candidate for dynamically mapping and load balancing not only existing MPP systems but also large distributed systems like the Internet, small cluster computers, and networks of workstations.

The network properties of double and triple fixed step graphs are considered. We determine that the broadcast times of double and triple fixed step graphs of diameter D are equal to D+2 and D+3, respectively. Some results on the embeddings of grids into these graphs with dilation 1 and 2 are given. For a triple fixed step graph we give a method to calculate the routing between any two vertices of the graph. Furthermore, we show that the diameter of the surviving route graph remains two for any set F of faults for |F|=5, which is optimum.

Let N be a closed connected smooth four-manifold with H₁(N; ℤ) = 0. Our main result is the following classification of the set E⁷(N) of smooth embeddings N → ℝ⁷ up to smooth isotopy. Haefliger proved that E⁷(S⁴) together with the connected sum operation is a group isomorphic to ℤ₁₂. This group acts on E⁷(N) by an embedded connected sum. Boéchat and Haefliger constructed an invariant ℵ: E⁷(N) → H₂(N;ℤ) which is injective on the orbit space of this action; they also described im(ℵ). We determine the orbits of the action: for u ∈ im(ℵ) the number of elements in ℵ^-1(u) is GCD (u/2, 12) if u is divisible by 2, or is GCD(u, 3) if u is not divisible by 2. The proof is based on Kreck's modified formulation of surgery.

Given a manifold N and a number m, we study the following question: is the set of isotopy classes of embeddingsN → S^mfinite? In case when the manifold N is a sphere the answer was given by A. Haefliger in 1966. In case when the manifold N is a disjoint union of spheres the answer was given by D. Crowley, S. Ferry and the author in 2011. We consider the next natural case when N is a product of two spheres. In the following theorem, FCS(i, j) ⊂ ℤ² is a specific set depending only on the parity of i and j which is defined in the paper.

Theorem.Assume thatm > 2p + q + 2andm < p + 3q/2 + 2. Then the set of isotopy classes ofC¹-smooth embeddingsS^p × S^q → S^mis infinite if and only if eitherq + 1orp + q + 1is divisible by 4, or there exists a point(x, y)in the setFCS(m - p - q, m - q)such that(m - p - q - 2)x + (m - q - 2)y = m - 3.

Our approach is based on a group structure on the set of embeddings and a new exact sequence, which in some sense reduces the classification of embeddings S^p × S^q → S^m to the classification of embeddings S^p+q ⊔ S^q → S^m and D^p × S^q → S^m. The latter classification problems are reduced to homotopy ones, which are solved rationally.

We show that, for a closed orientable $n$-manifold, with $n$ not congruent to 3 modulo 4, the existence of a CR-regular embedding into complex $(n-1)$-space ensures the existence of a totally real embedding into complex $n$-space. This implies that a closed orientable $(4k+1)$-manifold with non-vanishing Kervaire semi-characteristic possesses no CR-regular embedding into complex $4k$-space. We also pay special attention to the cases of CR-regular embeddings of spheres and of simply-connected 5-manifolds.

We present a novel $C^0$-characterization of symplectic embeddings and diffeomorphisms in terms of Lagrangian embeddings. Our approach is based on the shape invariant, which was discovered by Sikorav and Eliashberg, intersection theory and the displacement energy of Lagrangian submanifolds, and the fact that non-Lagrangian submanifolds can be displaced immediately. This characterization gives rise to a new proof of $C^0$-rigidity of symplectic embeddings and diffeomorphisms. The various manifestations of Lagrangian rigidity that are used in our arguments come from $J$-holomorphic curve methods. An advantage of our techniques is that they can be adapted to a $C^0$-characterization of contact embeddings and diffeomorphisms in terms of coisotropic (or pre-Lagrangian) embeddings, which in turn leads to a proof of $C^0$-rigidity of contact embeddings and diffeomorphisms. We give a detailed treatment of the shape invariants of symplectic and contact manifolds, and demonstrate that shape is often a natural language in symplectic and contact topology. We consider homeomorphisms that preserve shape, and propose a hierarchy of notions of Lagrangian topological submanifold. Moreover, we discuss shape-related necessary and sufficient conditions for symplectic and contact embeddings, and define a symplectic capacity from the shape.

We present an optimal embedding of a honeycomb network (honeycomb mesh and honeycomb torus) of size n into a hypercube with expansion ratio of when n is a power of two. When n is not a power of two, the expansion is , which we conjecture to be near optimal. For a honeycomb mesh, the dilation of the embedding is 1. For a honeycomb torus, the dilation can be as large as 2⌈log n⌉+3, because of the extra links connecting symmetric opposite nodes of degree two. A honeycomb network, built recursively using hexagon tessellation, is a multiprocessor interconnection network, and also a Cayley graph, and it is better than the planar mesh with the same number of nodes in terms of degree, diameter, number of links, and bisection width.