NIC-平面图中的轻边存在性及其定向染色

如果一个图[G]画在平面上有交叉[c],则该交叉可以与产生它的两条边所关联的4个顶点所构成的点集合[{v1,v2,v3,v4}]建立一个对应关系[θ:c→{v1,v2,v3,v4}]。如果对于[G]中任何两个不同的交叉（如果存在的话）[c1]与[c2]都有[|θ(c1)?θ(c2)|≤1],则称图[G]为NIC-平面图。证明了每个围长至少为5且最小度为4的NIC-平面图含有一条边,其2个顶点的度数都是4,从而每个围长至少为5的NIC-平面图的定向染色数至多为67。     

MV代数的子代数及相关重言式之间的关系

对MV单位区间[[0,1]]和n-值MV代数[Ln]的子代数的结构问题及其上重言式之间的关系进行了较为细致的研究。主要结论是：如果MV单位区间[[0,1]]的子代数[M]同构于n-值MV代数[Ln]的子代数,那么,存在正整数[m]满足[(m-1)|(n-1)]使得[M=Lm];如果[M]是MV单位区间[[0,1]]的子代数,那么或[M]为有限MV代数[Ln],或[M]为区间[[0,1]]上包含[{0,1}]的稠密集;若正整数[n-1]可分解为[(m1-1)(m2-1)?(mt-1)],其中[m1-1,m2-1,?,mt-1]是两两互素的正整数,则[Ln]是[Lm1,Lm2,?,Lmt]生成的MV代数;[T([0,1])=n=2∞T(Ln)],其中[T(M)]表示MV代数[M]上全体重言式之集合。     

带有条件故障边的k元2方体的圈嵌入

[k]元[n]方体已经成为分布式储存并行系统最常用的网络拓扑结构。研究带有条件故障边的[k]元2方体的圈嵌入问题,证明了在[k≥4]为偶整数的[k]元2方体中,若其故障边数不超过3且每个顶点至少与两条非故障边相关联,那么该[k]元2方体存在长度在4到[k2]间的任意偶长的无故障圈。     

k元n方体网络的子网络可靠性

并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用。为了衡量基于[k]元[n]方体网络构建的并行计算机系统的容错能力,研究了边故障模型下[k]元[n]方体网络中[k]元[(n-1)]方体子网络的可靠性。当[k(k≥3)]为奇数时,分别在固定划分模式和灵活划分模式下得出了[k]元[n]方体网络中不同数目的[k]元[(n-1)]方体子网络保持无故障状态的平均失效时间的计算公式,并通过仿真实验验证了理论结果的精确性。研究表明,当[k]为奇数的[k]元[n]方体网络中有边故障发生时,相比固定划分模式,在灵活划分模式下不同数目的[k]元[(n-1)]方体子网络保持无故障状态的平均失效时间更大。     

故障广义4元n方体中不同长度的路嵌入

k元n方体是传输信息的一种重要网络,研究含有故障点的广义4元n方体。证明了当其故障点数f≤n-1时,对每个整数l∈{2n-1,2n,…,4ⁿ-f-1},任意两个非故障点之间存在长度为l的无故障路。     

联图[K1,1,3∨Cn]的交叉数

联图[G∨H]表示将[G]的每个顶点与[H]的每个顶点连边得到的图。在Klesc给出的联图[K1,1,2∨Cn]的交叉数为[Z(4,n)+n2+3]的基础上,根据联图的相关性质,运用反证法和排除法,得到了联图[K1,1,3∨Cn]与[{K1,1,3+e}∨Cn]的交叉数均为[Z(5,n)+n+n2+4]。并假设在Zarankiewicz猜想成立的前提下,提出对[K1,1,m∨Cn(m≥4)]的交叉数的一个猜想：[cr?(K1,1,m∨Cn)≥Z(m+2,n)+m+12m2n2+m2m-12n2+][m+1,m≥4]。     

极大限制边连通网络的充分条件

限制边连通度是度量网络可靠性的重要参数。设[G]是一个边集为[E]的连通网络。称一个边集合[S?E]是一个限制边割,如果[G-S]是不连通的且每个分支至少有两个顶点。网络[G]的限制边连通度,记为[λ'],定义为[G]的最小限制边割的基数。设[d(v)]表示顶点[v]的度,[ξ=min{d(u)+d(v)-2:uv∈E}]表示[G]的最小边度。称网络[G]是极大限制边连通的,如果[λ'=ξ]。给出了网络是极大限制边连通的一些充分条件。     

一种新型多维数据空间放置算法

介绍了一种新型的多维数据空间放置算法——SMDPA.该算法使用数据超方体的先验被访问概率以及访问之间的相似度放置超方体.即使在数据超方体的被访问频率不满足均匀分布的情况下,该算法可以有效地放置超方体.模拟结果证明,该算法较传统算法有更良好的性能.     

UCDOS大家学之六

(3)设置显示文字的大小(@h,w) h为将显示文字的高度,w为将显示汉字的宽度,英文字体的宽度为w/2。本设置不改变当前使用的字库。例:在当前位置显示96×96点陈大小的黑体“汉字”: @0,0 SAY chr(14)+‘[{@96,96=2汉字}]’ (4)选择显示文字时使用的字库(=n) n为将显示文字使用的字库编号,取值范围为     

边故障K元3立方体的二不交路覆盖

研究具有故障边的[k]元3立方体的非指定二不交路覆盖问题。证明了在具有至多3条故障边的[k]元3立方体[Qk3]中,任意给定两个源点和两个汇点,则存在两条顶点不交的路[P1]和[P2],分别连接一个源点和汇点,且[V(P1)?V(P2)=V(Qk3)]。     

交换超立方网中的最短路径路由算法

针对交换超立方网络的最短路由问题,提出一个交换超立方网中的最短路径路由算法.利用图论的方法,通过引进子网的概念,研究交换超立方网的拓扑性质,给出节点各边可进行最短路径路由的充要条件,得到其时间复杂度为O(s+t)2).理论分析和仿真结果表明,该算法可输出交换超立方网中任意两节点间的一条最短路径.     

A comparative study of topological properties of hypercubes andstar graphs

Undertakes a comparative study of two important interconnection network topologies: the star graph and the hypercube, from the graph theory point of view. Topological properties are derived for the star graph and are compared with the corresponding properties of the hypercube. Among other results, the authors determine necessary and sufficient conditions for shortest path routing and characterize maximum-sized families of parallel paths between any two nodes of the star graph. These parallel paths are proven of minimum length within a small additive constant. They also define greedy and asymptotically balanced spanning trees to support broadcasting and personalized communication on the star graph. These results confirm the already claimed topological superiority of the star graph over the hypercube     

A direct method for solving linear systems

In this work we propose a direct method for solving systems of linear equations which is based on a successive LU-decomposition of matrices of the form l + uv ^T . Simultaneously, the factors of an LU-decomposition of the coefficient matrix are obtained. A specific choice of the “rank-one decomposition” of the given matrix leads to a variant of the Gauss elimination process.     

<Emphasis Type="Italic">D</Emphasis>-decomposition technique state-of-the-art

It is a survey of recent extensions and new applications for the classical D-decomposition technique. We investigate the structure of the parameter space decomposition into root invariant regions for single-input single-output systems linear depending on the parameters. The D-decomposition for uncertain polynomials is considered as well as the problem of describing all stabilizing controllers of the certain structure (for instance, PID-controllers) that satisfy given H _∞-criterion. It is shown that the D-decomposition technique can be naturally linked with M-Δ framework (a general scheme for analysis of uncertain systems) and it is applicable for describing feasible sets for linear matrix inequalities. The problem of robust synthesis for linear systems can be also treated via D-decomposition technique.     

Study of D-decompositions by the methods of computational real-valued algebraic geometry

New methods to study the D-decomposition with the use of the computational realvalued algebraic geometry were proposed. The number of domains of D-decomposition for the polynomial parametric families of polynomials and matrices was estimated. This technique which requires construction of the Gr?bner bases and cylindrical decomposition sometimes proves to be more precise than the traditional technique. The symbolic calculation system Maple v.14 and, in particular, its package RegularChains are used.     

LU-decomposition and numerical structure for solving large sparse nonsymmetric linear systems

In this work, the solution of a large sparse linear system of equations with an arbitrary sparsity pattern is obtained by using LU-decomposition method as well as numerical structure approach. The LU-decomposition method is based on Doolittle's method while the numerical structure approach is based on Cramer's rule. The numerical structure approach produces direct solution without facing fill-in problems as encountered in LU-decomposition. In order to reduce the ‘fill-ins’ in the decomposition, the powers of a Boolean matrix, obtained from the coefficient matrix A are taken so that the ‘fill-ins’ in the structure of A can be known in advance. The position of fill-ins in A are thus determined in the best choice manner, that is, it is very effective and memory-wise cheap. We also outline a method by using numerical structure with reduced computation efforts.Finally, experiments are performed on eight examples to compare the efficiency of the proposed methods. The results obtained are reported in a table. It is found that the LU-decomposition method is much better than numerical structure. The usefulness of numerical structure approach is also discussed.     

局部k-子立方连通的超立方网络中的广播容错算法

基于局部k-子立方体连通性的概念，提出了在局部k-子立方连通的超立方体中的，“播路由算法该算法是分布的、基于局部信息的，在容错性上有了很大的提高，能在线性时间内构造超立方体H1中接近最优的路径。     

PARALLEL PROCESSING FOR CHROMOSOME RECONSTRUCTION FROM PHYSICAL MAPS - A CASE STUDY OF MIMD PARALLELISM ON THE HYPERCUBE

Ordering clones from a genomic library into physical maps of whole chromosomes presents a pivotal computational problem in genetics. Previous research has shown the physical mapping problem to be isomorphic to the NP-complete Optimal Linear Arrangement (OLA) problem for which no polynomial-time algorithm for determining the optimal solution is known. Serial implementations of stochastic global optimization techniques such as simulated annealing yielded very good results but proved computationally intensive. The design, analysis and implementation of coarse-grained parallel MIMD algorithms for simulated annealing on the Intel iPSC/860 hypercube is presented. Data decomposition and control decomposition strategies based on Markov chain decomposition, perturbation methods and problem-specific annealing heuristics are proposed and applied to the physical mapping problem. A suite of parallel algorithms are implemented on an 8-node Intel iPSC/860 hypercube, exploiting the nearest-neighbor communication pattern on the Boolean hypercube topology. Convergence, speedup and scalability characteristics of the various parallel algorithms are analyzed and discussed. Results indicate a deterioration of performance when a single Markov chain of solution states is distributed across multiple processing elements in the Intel iPSC/860 hypercube.     

基于NPV广义超立方体最佳容错路由算法

在网络可靠性研究中,设计较好的容错路由策略、尽可能多地记录系统中最优通路信息,一直是一项重要的研究工作.超立方体系统的容错路由算法分为可回溯算法和无回溯算法.一般说来,可回溯算法的优点是容错能力强:只要消息的源节点和目的节点有通路,该算法就能够找到把消息传递到目的地的路径;其缺点是在很多情况下传递路径不能按实际存在的最短路径传递.其代表是深度优先搜索(DFS)算法.无回溯算法是近几年人们比较关注的算法.该算法通过记录各邻接节点的故障信息,给路由算法以启发信息,使消息尽可能按实际存在的最短路径传递.这些算法的共同缺点是只能计算出Hamming距离不超过n的路由.在n维超立方体系统连通图中,如果系统存在大量的故障,不少节点对之间的最短路径大于n,因此,这些算法的容错能力差.提出了一个实例说明采用上述算法将遗失60%的路由信息.另外,由于超立方体的结构严格,实际中的真正超立方体系统不多.事实上,不少的网络系统可转换为具有大量错误节点和错误边的超立方体系统.因此,研究能适应具有大量错误节点和错误边的超立方体系统的容错路由算法是一个很有实际价值的工作.研究探讨了:(1) 定义广义超立方体系统;(2) 在超立方体系统中提出了节点通路向量(NPV)概念及其计算规则;(3) 提出了中转点技术,使得求NPV的计算复杂度降低到O(n);(4) 提出了基于NPV的广义超立方体系统最佳容错路由算法(OFTRS),该算法是一种分布式的和基于相邻节点信息的算法.由于NPV记录了超立方体系统全部最优通路和次最优通路的信息,在具有大量故障的情况下,它不会遗漏任何一条最优通路和次最优通路信息,从而实现了高效的容错路由.在这一点上,它优于其他算法.