树状网络上带度约束的k-tree core问题

考虑到在实际应用中,由于计算机和通信网络中一般每个设备的处理能力是有限的,在k-tree core问题的基础上,提出了同时带有度约束的k-tree core问题,即k-tree core中的每个节点在子树中的度不超过给定常数q,记为q-DTC（k）（Degree constrained Tree Core）。利用动态规划的方法,采用最优化原则先找出文中所定义的局部根核集,然后利用贪婪思想对不满足度限制的节点所在的分支加以删减,对无权树和赋权树得到了复杂度分别为O（kn）和O（max{n log n,kn}）多项式时间算法,其中n是树的节点数。     

一种用于大整数因数分解的多相位粒子群算法

如果大整数N的两个因数p与q满足p=x_p×D+y_p,q=x_q×D+y_q,D>y_p×y_q约束,那么该大整数N将有可能被轻易分解。因此,根据该约束及相关定理,提出了一种用于求解大整数因数分解问题（IFP）的尾数多相位粒子群搜索算法,MMPPSO。数值实验证明,MMPPSO算法对IFP具有良好的求解能力。同时,建议依赖于大整数N分解问题的密码系统做上述约束条件测试,从而保证密钥和系统的安全性。     

软件可靠性预测的ARIMA方法研究

对基于求和自回归滑动平均模型（ARIMA模型）的软件可靠性预测方法进行了研究,提出了将软件可靠性失效数据看作时间序列,通过建立相应的ARIMA（p,d,q）模型来进行预测的方法。对该方法的基本思想、模型表述、建模流程进行了详细介绍,并依据上述方法选用Musa经典数据集中的Project SS2中的数据进行了预测,结果表明预测的准确性较高,说明该方法适用于软件可靠性预测。     

ARIMA模型在农产品价格预测中的应用

利用农产品价格时间序列的当前值和过去值准确预报未来值,将有利于正确引导农产品流通和农业生产,实现农产品区域供求平衡,并为政府和农户提供结构调整的依据。针对农产品价格这一重要问题,以白菜月价格数据为例,构建非平稳时间序列ARIMA（p,d,q）模型并预测白菜未来的月价格。结果表明ARIMA（0,1,1）模型能很好地模拟并预测白菜月价格趋势,为农产品市场信息的准确预测提供重要方法。     

一类层次双环网络的构造及其路由算法

高效互联网络的拓扑结构一直是人们关注的热点问题。提出了一类层次双环互联网络HDRN（k）,给出了HDRN（k）网络的构造方法,研究了它的性质,并且通过与相关网络的比较,证实了HDRN（k）具有好的连接性、短的直径以及简单的拓扑结构,是一种实用的互联网络。另外,讨论了HDRN（k）网络的路由性质,设计了点点路由和Broadcast路由算法,证明了这两种路由算法的通信效率与层次环网络上对应算法的通信效率相比均有明显的提高。综上所述,HDRN（k）是一种具有良好拓扑性质的新型互联网络。     

一类不平衡Feistel密码的安全性能分析

为评估一类不平衡Feistel密码的安全性能,通过列举的方法,对该密码抵抗差分密码分析和线性密码分析的能力进行了深入的研究。在轮函数是双射的假设条件下,证明了3,4,6,8,10,2r（r≥3）轮密码分别至少有1,1,3,4,5,r个轮函数的输入差分非零,从而若设轮函数的最大差分和线性逼近的概率分别为p和q,则2r（r≥3）轮密码的差分特征和线性特征的概率分别以pr和qr为上界。     

de Bruijn序列查寻表标签的k位修正构造法

de Bruijn序列的结构是一个查寻表,其核心是它的表标签。因此构造出查寻表标签对于生成de Bruijn序列十分重要。给出两种k位修正构造法。方法1为k位提升构造法,即对大部分节点将其第k（k=1,2,…,n-1）位提升一个定值c（1≤c≤m）,来作为该节点的标签。方法2为k位收缩构造法,即对大部分节点将其第k（k=1,2,…,n-1）位向定值r（0≤r≤m）收缩,来作为该节点的标签。这些方法构造的查寻表标签数随着m,n增长而成指数式增长。与定值构造法一样,在局部看是有效的,但与查寻表标签本身数目的惊人增长比较起来就很渺小。方法2与定值标签构造法比较其速度提高了关于m,n的指数式倍。     

2r-正则图连通圈网络的Hamilton分解

互连网络是超级计算机的重要组成部分。互连网络通常模型化为一个图,图的顶点代表处理机,图的边代表通信链路。2010年师海忠提出互连网络的正则图连通圈网络模型,设计出了多种互连网络,也提出了一系列猜想。文中证明了2r -正则图连通圈网络可分解为边不交的一个Hamilton圈和一个完美对集的并,从而证明了当原图为2r-正则连通图时,这一系列猜想成立。     

关于互连网络的几个猜想

n-立方体是著名的互连网络,星图、煎饼图和冒泡排序图是由凯莱图模型设计出来的重要的互连网络。对换树（transposition tree）的凯莱图是一类特殊的凯莱图,星图和冒泡排序图分别是对换树为星和路的凯莱图。给出了关于n-立方体、星图、煎饼图、冒泡排序图和对换树的凯莱图的各一个猜想;提出了对换图的凯莱图的概念,进而由这一概念设计出了两个互连网络——圈图和轮图,并证明冒泡排序图和星图分别可嵌入圈图和轮图。     

一种二值图像的阈值可视密码方案

目前提出的许多关于二值可视密码方案的论文都致力于研究在可视秘密共享方案里如何使像素扩展比较小或恢复图像的对比度比较高的问题。基于Shamir的秘密共享方案的思想,提出一种新的二值图像（k,n）-VCS可视密码方案。该方案利用二元域上线性方程组解的特征及多层（k,k）-VCS构造基础矩阵S⁰,S¹,给出一个强的访问结构,从而获得（k,n）-VCS可视密码方案更小的像素扩展。     

A Group Construction Method with Applications to Deriving Pruned Interconnection Networks

A number of low degree and, thus, low complexity, Cayley-graph interconnection structures, such as honeycomb and diamond networks, are known to be derivable by systematic pruning of 2D or 3D tori. In this paper, we extend these known pruning schemes via a general algebraic construction based on commutative groups. We show that, under certain conditions, Cayley graphs based on the constructed groups are pruned networks when Cayley graphs of the original commutative groups are kD tori. Thus, our results offer a general mathematical framework for synthesizing and exploring pruned interconnection networks that offer lower node degrees and, thus, smaller VLSI layout and simpler physical packaging. Our constructions also lead to new insights, as well as new concrete results, for previously known interconnection schemes such as honeycomb and diamond networks     

A new family of interconnection networks of fixed degree three

A new family of interconnection networks WGn is proposed, that is constant degree 3 Cayley graph, and is isomorphic to a Cayley graph of the wreath product Z2 Sn when the generator set is chosen properly. Its different algebraic properties is investigated and a routing algorithm is given with the diameter upper bounded by 3n2 - 6n 4. The embedding properties and the fault tolerance are devired. In conclusion, we present a comparison of some familiar networks with constant degree 3.     

Cyclic-cubes: a new family of interconnection networks of evenfixed-degrees

We introduce a new family of interconnection networks that are Cayley graphs with fixed degrees of any even number greater than or equal to four. We call the proposed graphs cyclic-cubes because contracting some cycles in such a graph results in a generalized hypercube. These Cayley graphs have optimal fault tolerance and logarithmic diameters. For comparable number of nodes, a cyclic-cube can have a diameter smaller than previously known fixed-degree networks. The proposed graphs can adopt an optimum routing algorithm known for one of its subfamilies of Cayley graphs. We also show that a graph in the new family has a Hamiltonian cycle and, hence, there is an embedding of a ring. Embedding of meshes and hypercubes are also discussed     

The Cayley network of expanded Pancake graphs

Signed permutation group has important applications in genome rearrangement as well as the construction of networks. In this paper, we propose a new interconnection network named extended Pancake graph, we investigate its topological properties, and give a routing algorithm with the diameter upper bounded by 2n?1. Some embedding properties are also derived. In conclusion, we present a comparison of some familiar networks with the Cayley graph EP _n .     

边故障[k]元[n]立方体的超级哈密顿交织性

[k]元[n]立方体（记为[Qkn]）是优于超立方体的可进行高效信息传输的互连网络之一。[Qkn]是一个二部图当且仅当[k]为偶数。令[G[V0,V1]]是一个二部图,若（1）任意一对分别在不同部的顶点之间存在一条哈密顿路,且（2）对于任意一点[v∈Vi],其中[i∈{0,1}],[V1-i]中任意一对顶点可以被[G[V0,V1]-v]中的一条哈密顿路相连,则图[G[V0,V1]]被称为是超级哈密顿交织的。因为网络中的元件发生故障是不可避免的,所以研究网络的容错性就尤为重要。针对含有边故障的[Qkn],其中[k4]是偶数且[n2],证明了当其故障边数至多为[2n-3]时,该故障[Qkn]是超级哈密顿交织图,且故障边数目的上界[2n-3]是最优的。     

Comments on “A new family of Cayley graph interconnectionnetworks of constant degree four”

For original paper see Vadapalli and Srimani, ibid., vol. 7, no. 1, p 26-32, 1996, where the authors have proposed a new family of Cayley graph interconnection networks of constant degree four. Our comments show that their proposed graph is not new but is the same as the wrap-around butterfly graph. The structural kinship of the proposed graph with the de Bruijn graph is also discussed     

Macro-star networks: efficient low-degree alternatives to stargraphs

We propose a new class of interconnection networks, called macro-star networks, which belong to the class of Cayley graphs and use the star graph as a basic building module. A macro-star network can have node degree that is considerably smaller than that of a star graph of the same size, and diameter that is sublogarithmic and asymptotically within a factor of 1.25 from a universal lower bound (given its node degree). We show that algorithms developed for star graphs can be emulated on suitably constructed macro-stars with asymptotically optimal slowdown. This enables us to obtain through emulation a variety of efficient algorithms for the macro-star network, thus proving its versatility. Basic communication tasks, such as the multimode broadcast and the total exchange, can be executed in macro-star networks in asymptotically optimal time under both the single-port and the all-port communication models. Moreover, no interconnection network with similar node degree can perform these communication tasks in time that is better by more than a constant factor than that required in a macro-star network. We show that macro-star networks can embed trees, meshes, hypercubes, as well as star, bubble-sort, and complete transposition graphs with constant dilation. We introduce several variants of the macro-star network that provide more flexibility in scaling up the number of nodes. We also discuss implementation issues and compare the new topology with the star graph and other popular topologies     

Task assignment in Cayley interconnection topologies

Based on the Cayley graph framework for the generation and evaluation of multiprocessor interconnection topologies, an application dependent task mapping problem is addressed. We start with interconnection topologies considered attractive from a graph theoretical point of view. Given such a topology together with an application dependent task communication profile, the problem addressed in this paper is to find an optimal task-to-processor assignment. Such a mapping yields for the given interconnection topology and the given profile a minimal expected communication path length and therefore a minimal number of data transfer steps between the physical processing elements of a multiprocessor machine. At first, the Cayley graph approach is briefly outlined. We demonstrate the potential of Cayley graphs for a systematic generation framework aiming at node-symmetric interconnection topologies for a given number of processing elements each equipped with a constant number of communication channels. Cayley graphs found most attractive within a large set of generated graphs are compared to prominent interconnection topologies like, for example, hypercubes. Later on, it is shown that the problem of the optimal task-to-processor assignment, being a special case of the well-known quadratic assignment problem, is still NP-hard. Consequently, any practically relevant mapping algorithm can be expected to produce at best near-optimal solutions for reasonable problem sizes beyond approximately 10 nodes. We present two fundamentally different mapping approaches, namely a straightforward greedy mapping and a more sophisticated algorithm using simulated annealing techniques as known from artificial intelligence applications. For both approaches, we elaborate on their relative performance as well as, where feasible, on the question of suboptimality.