A RIGOROUS PROOF ON CIRCULAR WIRELENGTH FOR HYPERCUBES

We study embeddings of the n-dimensional hypercube into the circuit with 2nvertices.We prove that the circular wirelength attains a minimum by gray coding;that was called the CT conjecture by Chavez and Trapp(Discrete Applied Mathematics,1998).This problem had claimed to be settled by Ching-Jung Guu in her doctoral dissertation“The circular wirelength problem for hypercubes”(University of California,Riverside,1997).Many argue there are gaps in her proof.We eliminate the gaps in her dissertation.

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2n个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,52n-5/3}个波长.而在环网络上,实现该通信模式需要复用N/3+N/12个波长,比已有算法需要复用N/3+N/4个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.

基于Hypercube的最长导出路算法

超立方体(Hypercube)网络是多处理机系统中常见的一种互连网络。文中提出Hypercube中最长导出路的概念,然后给出一种能改善多处理机系统中传输容错性的最长导出路算法,最后给出该算法的C++实现。

Hypercube中LIP长度的上下界估计

给出了超立方体网络中LIP容错模型的上下界估计及一个非常有意义的猜想,并且结合已有结果对上下界及猜想进行了验证。验证结果表明,对LIP的上下界估计,当n较小时还是比较好的;此外,猜想当n=2,3,4,5,6,7时均严格成立,具有非常好的理论价值和实际意义,有待进一步证明。

Diagnosabilities of exchanged hypercube networks under the pessimistic one-step diagnosis strategy

The exchanged hypercube EH（s, t） （where s ≥ 1 and t ≥ 1） is obtained by systematically reducing links from a regular hypercube Q,＋t＋l. One-step diagnosis of exchanged hypercubes which involves only one testing phase during which processors test each other is discussed. The diagnosabilities of exchanged hypercubes are studied by using the pessimistic one-step diagno- sis strategy under two kinds of diagnosis models： the PMC model and the MM model. The main results presented here are the two proofs that the degree of diagnosability of the EH（s, t） under pessimistic one-step tl/tl fault diagnosis strategy is 2s where I ≤ s ≤ t （respectively, 2t, where 1 ≤ t ≤ s） based on the PMC model and that it is also 2s where 1 ≤ s ≤ t （respectively, 2t, where 1 ≤ t ≤ s） based on the MM＊ model.

PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS

Let Qn,k （n 〉 3, 1 〈 k ≤ n - 1） be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges, fv and fe be the numbers of faulty vertices and faulty edges, respectively. In this paper, we give three main results. First, a fault-free path P[u, v] of length at least 2n - 2fv - 1 （respectively, 2n - 2fv - 2） can be embedded on Qn,k with fv ＋ f≤ n- 1 when dQn,k （u, v） is odd （respectively, dQ,~,k （u, v） is even）. Secondly, an Q,,k is （n - 2） edgefault-free hyper Hamiltonianaceable when n （ 3） and k have the same parity. Lastly, a fault-free cycle of length at least 2n - 2fv can be embedded on Qn,k with f~ 〈 n - 1 and fv＋f≤2n-4.

On Restricted Connectivity and Extra Connectivity of Hypercubes and Folded Hypercubes

Given a graph G and a non-negative integer h, the h-restricted connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, in which at least h neighbors of any vertex is not included, if any, whose deletion disconnects G and every remaining component has the minimum degree of vertex at least h; and the h-extra connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, if any, whose deletion disconnects G and every remaining component has order more than h. This paper shows that for the hypercube Qn and the folded hypercube FQn, κ1（Qn）=κ（1）（Qn）=2n-2 for n≥3, κ2（Qn）=3n-5 for n≥4, κ1（FQn）=κ（1）（FQn）=2n for n≥4 and κ（2）（FQn）=4n-4 for n≥8.

t/k-fault diagnosis algorithm of n-dimensional hypercube network based on the MM*model

Compared with accurate diagnosis, the system’s selfdiagnosing capability can be greatly increased through the t/kdiagnosis strategy at most k vertexes to be mistakenly identified as faulty under the comparison model, where k is typically a small number. Based on the Preparata, Metze, and Chien(PMC)model, the n-dimensional hypercube network is proved to be t/kdiagnosable. In this paper, based on the Maeng and Malek(MM)*model, a novel t/k-fault diagnosis(1≤k≤4) algorithm of ndimensional hypercube, called t/k-MM*-DIAG, is proposed to isolate all faulty processors within the set of nodes, among which the number of fault-free nodes identified wrongly as faulty is at most k. The time complexity in our algorithm is only O(2~n n~2).

(d,m)-DOMINATING NUMBERS OF HYPERCUBE

This paper shows that the (d,m)-dominating number of the m-dimensional hypercube Q m(m≥4) is 2 for any integer d.[FK(W1*1。*2]m2[FK(W1*1。*2]+2≤d≤m.

Application of the optimal Latin hypercube design and radial basis function network to collaborative optimization

Improving the efficiency of ship optimization is crucial for modem ship design. Compared with traditional methods, multidisciplinary design optimization （MDO） is a more promising approach. For this reason, Collaborative Optimization （CO） is discussed and analyzed in this paper. As one of the most frequently applied MDO methods, CO promotes autonomy of disciplines while providing a coordinating mechanism guaranteeing progress toward an optimum and maintaining interdisciplinary compatibility. However, there are some difficulties in applying the conventional CO method, such as difficulties in choosing an initial point and tremendous computational requirements. For the purpose of overcoming these problems, optimal Latin hypercube design and Radial basis function network were applied to CO. Optimal Latin hypercube design is a modified Latin Hypercube design. Radial basis function network approximates the optimization model, and is updated during the optimization process to improve accuracy. It is shown by examples that the computing efficiency and robustness of this CO method are higher than with the conventional CO method.

VERTEX-FAULT-TOLERANT CYCLES EMBEDDING ON ENHANCED HYPERCUBE NETWORKS

In this paper, we study the enhanced hypercube, an attractive variant of the hypercube and obtained by adding some complementary edges from a hypercube, and focus on cycles embedding on the enhanced hypercube with faulty vertices. Let Fu be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k （n ≥ 3, 1 ≤ k 〈≤n - 1）. When IFvl = 2, we showed that Qn,k - Fv contains a fault-free cycle of every even length from 4 to 2n - 4 where n （n ≥ 3） and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2n - 4, simultaneously, contains a cycle of every odd length from n-k ＋ 2 to 2^n-3 where n （≥ 3） and k have the different parity. Furthermore, when ｜Fv｜ = fv ≤ n - 2, we prove that there exists the longest fault-free cycle, which is of even length 2^n - 2fv whether n （n ≥ 3） and k have the same parity or not; and there exists the longest fault-free cycle, which is of odd length 2^n - 2fv ＋ 1 in Qn,k - Fv where n （≥ 3） and k have the different parity.

On the extra edge-connectivity of hypercubes

The classical hypercube structure is a popular topological architecture in parallel computing environments and a large number of variations based on the hypercube were posed in the past three decades. Reliability evaluation of systems is important to the design and maintenance of multiprocessor systems. The h-extra edge-connectivity of graph G（V, E） is a kind of measure for the reliability of interconnection systems, which is defined as the minimum cardinality of a subset of edge set, if any, whose deletion disconnects G and such that every re- maining component has at least h vertices. This paper shows that the h-extra edge-connectivity 2n-1 2n-1 of the hypercube Qn is a constant 2n-1 for 2n-1/3≤ h2n-1, and n ≥ 4, which extends the result of [Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes, Discrete Applied Mathematics, 2013, 161（16）： 2753-2757].

Multiply-twisted Hypercube with Four or Less Dimensions is Vertex-transitive

P Kulasinghe and S Bettayeb showed that any multiply-twisted hypercube withfive or more dimensions is not vertex-transitive. This note shows that any multiply-twistedhypercube with four or less dimensions is vertex-transitive, and that any multiply-twistedhypercube with three or larger dimensions is not edge-transitive.

Folded Hypercubes在PMC模型下的可诊断数

可诊断数是衡量多处理器系统可靠性的一个重要参数。文中通过对折叠立方体的可诊断性研究,证明了在PMC模型下,折叠立方体是(n+2)-可诊断的(n≥3),且是(2n+2)/(2n+2)-可诊断的(n≥4)。

Restricted-Faults Identification in Folded Hypercubes under the PMC Diagnostic Model

System-level fault identification is a key subject for maintaining the reliability of multiprocessor interconnected systems. This task requires fast and accurate inferences based on big volume of data, and the problem of fault identification in an unstructured graph has been proved to be NP-hard （non-deterministic polynomial-time hard）. In this paper, we adopt the PMC diagnostic model （first proposed by Preparata, Metze, and Chien） as the foundation of point-to-point probing technology, and a system contains only restricted-faults if every of its fault-free units has at least one fault-free neighbor. Under this condition we propose an efficient method of identifying restricted-faults in the folded hypercube, which is a promising alternative to the popular hypercube topology.

A Time-Space Optimal Parallel Sorting on a Hypercube

In this paper we discuss a parallel sorting algorithm on a hypercube. Its time complexity is O(n logn/p) +O(n). Here, P is the number of processors available and n, the amount of items to be sorted. Take the problem of time-space optimization into consideration, when P≤ O(log n), this algorithm is both timespace optimal and cost optimization. But this means only speedup is O(P) and it is not linear speedup. Therefore, we further discuss relevant parallel efficiency problems.

Multidisciplinary Design and Optimization of Satellite Launch Vehicle Using Latin Hypercube Design of Experiments

The design of new Satellite Launch Vehicle （SLV） is of interest, especially when a combination of Solid and Liquid Propulsion is included. Proposed is a conceptual design and optimization technique for multistage Low Earth Orbit （LEO） bound SLV comprising of solid and liquid stages with the use of Genetic Algorithm （GA） as global optimizer. Convergence of GA is improved by introducing initial population based on the Design of Experiments （DOE） Technique. Latin Hypercube Sampling （LHS）-DOE is used for its good space filling properties. LHS is a stratified random procedure that provides an efficient way of sampling variables from their multivariate distributions. In SLV design minimum Gross Lift offWeight （GLOW） concept is traditionally being sought. Since the development costs tend to vary as a function of GLOW, this minimum GLOW is considered as a minimum development cost concept. The design approach is meaningful to initial design sizing purpose for its computational efficiency gives a quick insight into the vehicle performance prior to detailed design.

Boolean Automorphisms of a Hypercube Coincide with the Linear Isometries

Boolean homomorphisms of a hypercube, which correspond to the morphisms in the category of finite Boolean algebras, coincide with the linear isometries of the category of finite binary metric vector spaces.

On Embedding of m-Sequential k-ary Trees into Hypercubes

In this paper, we present an algorithm for embedding an m-sequential k-ary tree into its optimal hypercube with dilation at most 2 and prove its correctness.

On Certain Connected Resolving Parameters of Hypercube Networks

Given a graph , a set is a resolving set if for each pair of distinct vertices there is a vertex such that . A resolving set containing a minimum number of vertices is called a minimum resolving set or a basis for . The cardinality of a minimum resolving set is called the resolving number or dimension of and is denoted by . A resolving set is said to be a star resolving set if it induces a star, and a path resolving set if it induces a path. The minimum cardinality of these sets, denoted respectively by and are called the star resolving number and path resolving number. In this paper we investigate these re-solving parameters for the hypercube networks.