多处理器互连网络诊断性和容错性的细胞图自动机算法

本文将细胞图自动机概念引入多处理器互连网络，并用细胞图自动机设计了多处理器互连网络上的多项式级诊断和容错算法，从而给出了研究互连网络诊断性和容错性的另一种有效方法。     

细胞有向图自动机及算法

本文提出了细胞（ｄ１，ｄ２）－有向图自动机的定义，研究了怎样用它求得（ｄ１，ｄ２）－有向图的广度优先混合方向支撑树，单向树及强连通分量等问题并给出了相应的并行算法和时间复杂度分析。     

细胞（d1,d2）—有向图语言类在集合论运算下的封闭性

本文给出了细胞（ｄ１，ｄ２）－有图自动机类的定义及其接受语言（判断）类的定义，并讨论了该语言（判断）类在并、交、补等集合论运算下的封闭性。     

互连网络诊断性与容错性的细胞图自动机算法的串行模拟

本文对作者以前提出的细胞图自动机算法,给出了串行模拟结果,特别地给出了这些串行模拟程序对几种重要的互连网络如超立方体,交叉立体和Ｍｏｂｉｕｓ立方体模拟的一些具体结果及效率分析．     

交叉立方体互连网络的Hamilton连通性

交叉立方体互连网络是超立方体的一个变型,它有一些比超立方体更好的性质．本文证明了ｎ维交叉立方体ＣＱｎ的又一个超立方体所不具备的性质,即当ｎ≥１,ｎ≠２时,ＣＱｎ是Ｈａｍｉｌｔｏｎ连通的,并给出了当ｎ≥４时ＣＱｎ中任意两个顶点间Ｈａｍｉｌｔｏｎ路条数的一个下界４（２ｎ－１－２）∏ｎ－２ｉ＝３（２ｉ－２）２．     

细胞（d1，d2）－有向图语言类在集合论运算下的封闭性

本文给出了细胞（ｄ１，ｄ２）－有向图自动机类的定义及其接受的语言（判断）类的定义，并讨论了该语言（判断）类在并、交、补等集合论运算下的封闭性     

在细胞图自动机上寻找图的基本回路

将细胞自动结构推广到任意图结构，并用它解决图论中的问题，是细胞自动机理论在图论领域中的一个应用．本文给出了用细胞图自动机求任意连通图的所有基本回路的并行算法     

将圈嵌入交叉立方体及其算法

图嵌入技术是研究处理器互连网络的计算性能和任务分配的重要技术,是近年来并行处理领域的研究的热点之一,本文研究了交叉立方体互连网络上的圈嵌入问题。证明了任何长度为ｌ一能以扩张１嵌入交叉立方体ＣＱｎ并证明了ＣＱｎ包含２＾ｎ－ｋ个互不相交的长为２＾ｋ的圈,最后给一个Ｏ（ｌｌｏｇｌ）级的圈嵌入算法。     

关于加强超立方体互连网络的可诊断性的另一种证明方法

ｎ维加强超立方体是具有２＾ｎ个顶点，（ｎ＋１）２＾ｎ－１－正则图，它是通过对ｎ维超立方体增加２＾ｎ－１条边得到的。在「１」中证明了基于ＰＣＭ模型的ｎ维加强超立方体在精确诊断策略征是（ｎ＋１）－可诊断的，在悲观诊断策略下是（２ｎ）／（２ｎ）－可的，但在证明很繁琐。     

最小T－2倍树的构造算法

本文提出了对任意一棵树的顶点赋权使其满足一定约束条件的最小Ｔ－２倍树的定义，并给出了一个时间复杂度为Ｏ（ｎ２）的构造算法