边故障[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]是最优的。     

在PMC模型下单向k元n立方体的诊断度

图的连通度和诊断度是与互连网络的可靠性密切相关的两个参数,而[g]好邻连通度和[g]好邻诊断度是比连通度和诊断度更精确的指标。[k]元[n]立方体是多处理机系统的最常用网络之一,而单向[k]元[n]立方体是指具有单向边的[k]元[n]立方体。证明了当[k≥3,n≥3]时,单向[k]元[n]立方体在PMC模型下的[1]好邻连通度是[k(n-1)],诊断度是[n]且[1]好邻诊断度是[kn-1]。     

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

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

单向k-元n-立方体网络

单向[k]-元[n]-立方体是指具有单向边的[k]-元[n]-立方体互连网络拓扑。当网络包含的顶点数目较大时,比起传统的双向[k]-元[n]-立方体,单向?[k]-元[n]-立方体对通信硬件复杂性的要求更低一些。提出了[k]-元[n]-立方体的一个定向,使得定向后的单向[k]-元[n]-立方体[UQkn]有一些良好的性质。证明了[UQkn]是正则的,极大弧连通的,具有迭代结构的且[UQkn]的直径是小的。此外,提出了一个简单的多项式时间路由算法。     

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

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

外1-平面图的均匀边染色

图[G]的[s]-均匀边[k]-染色是指用[k]种颜色对图的边进行染色,使得图[G]的每个顶点所关联的任何两种颜色的边的条数至多相差[s]。使得对于每个不小于[k]的整数[t],图[G]都具有[s]-均匀边[t]-染色的最小整数[k]称为图[G]的[s]-均匀边色数阈值。文中证明了外1-平面图的1-均匀边色数阈值最多为5,不含有相邻的3圈的外1-平面图的均匀边色数阈值最多为4,外1-平面图的2-均匀边色数阈值恰好为1。     

一种交叉立方体网络的并行路由算法

Efe提出的交叉立方体是超立方体的一种变型,其某些性质优于超立方体。在高性能的并行计算机系统中,信息通过若干条内结点互不交叉的路径并行传输,这些路径的长度将直接影响并行计算的性能。该文提出了一种时间复杂度为o(n2)的交叉立方体网络并行路由算法,可输出源点u到目的点v的3条并行路径P0,P1,P2,并且满足：(1)|P0|= u到v的距离;(2)|Pi|≤u到v的距离+3(i=1,2)。这说明该算法是通信高效的。     

k元船方体网络的可靠性

[k]元[n]方体[Qkn]是设计大规模多处理机系统时最常用的互连网络拓扑结构之一。对于[1≤m≤n-1],设[F]是[Qkn]中的一个由非空点集[VF]和非空边集[EF]构成的故障集,满足[Qkn-F]中不存在[Qkn-m]且[VF]破坏的[Qkn-m]的集合与[EF]破坏的[Qkn-m]的集合互不包含。设[f＊（n,m）]是破坏[Qkn]中的所有子立方[Qkn-m]所需要的故障集[F]的最小基数。证明了对于奇数[k≥3],[fk（n,1）]为[k＋1],[fk（n,n-1）]为[kn-1-1＋n],[f＊（n,m）]的上下界分别为[Cm-1n-1km＋Cm-1n-2km-1]和[km]。举例说明了上界[Cm-1n-1km＋Cm-1n-2km-1]是最优的。     

求解必经点k条最优路径问题的粒子群优化算法

提出了一种解决指定必经点[k]条最优路径问题的粒子群优化算法。算法以[k]条最优路径集合作为优化目标,将粒子种群划分为[k]个子种群,通过各子种群的局部搜索和子种群间的相互协作,使种群在搜索过程中易于找到[k]条最优路径。为了提高含有多必经节点的初始生成路径的多样性,设计了基于弹性拉伸原理的种群初始化方法。在随机生成的26个节点65条边,50个节点262条边和80个节点410条边的拓扑图中,分别选取不同的源节点和目的节点,以及必经节点对算法进行了测试。数值实验结果表明,提出的算法在求解网络规模比较大、必经点数比较多的无环[k]条最优路径问题中具有比较好的性能。     

关于互连网络群论模型的一簇猜想

连通图生成的Cayley图是作为互连网络的群论模型提出来的概念。猜想:设G=(V,E)是具有顶点集{1,2,…,n}(n>2)和m条边的连通图。如果m=2r,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m－2k个完美对集的并;如果m=2r+1,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m－2k个完美对集的并。特别地,对于k=r和星网络,这个猜想的特殊情形是1998年由师海忠提出来的。     

General-demand disjoint path covers in a graph with faulty elements

A k-disjoint path cover of a graph is a set of k internally vertex-disjoint paths which cover the vertex set with k paths and each of which runs between a source and a sink. Given that each source and sink v is associated with an integer-valued demand d(v)≥1, we are concerned with general-demand k-disjoint path cover in which every source and sink v is contained in the d(v) paths. In this paper, we present a reduction of a general-demand disjoint path cover problem to an unpaired many-to-many disjoint path cover problem, and obtain some results on disjoint path covers of restricted HL-graphs and proper interval graphs with faulty vertices and/or edges.     

基于离散曲率的点云光顺算法

通过对三维激光扫描仪扫描测量数据的误差来源进行分析,设计了一种基于离散曲率的点云光顺处理的快速算法,该算法以曲率特征为索引,能够快速判别点云数据的特征点,对非特征点采用[w]邻域内[X,Y]两个方向拟合三次B样条曲线做光顺处理。最后通过实例证明了所提方法的有效性。     

基于全组合策略的多目标阴阳对算法

基于前沿的阴阳对优化算法（Front-based Yin-Yang-Pair Optimization,F-YYPO）是一种新颖的轻量级多目标优化算法,其利用两点--局部开发点[Pi1]和全局探索点[Pi2]在搜索过程中的迭代交换实现搜索。基于F-YYPO提出了一种改进的多目标优化算法F-ACYYPO。新算法对F-YYPO做了以下三方面的改进：（1）对多个目标函数进行全组合,以增强优化个体分布的均匀性;（2）引入已在YYPO算法中被证明有明显性能提高效果的缩放因子[α]自适应措施;（3）改进F-YYPO存档操作的更新方式。采用在2009年进化计算大会多目标优化算法竞赛中使用的UF测试套件以及PlatEMO平台下的DTLZ测试套件进行算法的性能评估,将F-ACYYPO与F-YYPO以及其他多种已知性能优良的多目标优化算法NSGA2、SPEA2、MOPSO、MOGWO、gamultiobj、MOEA\D、GDE3进行性能测试及比较,并通过两个综合性指标（反转世代距离IGD、超体积HV）和一个收敛性指标（世代距离GD）进行性能评价。实验结果表明,F-ACYYPO比F-YYPO具有更高的计算精度以及更快的收敛速度,并且与其他高性能多目标算法相比,F-ACYYPO表现出了很强的竞争性,在综合性能指标下有将近超1/2的测试用例占优。     

时域鲁棒设计的新方法──［P］和［V］·［V~－1］的极小化

本文讨论在极点配置的约束下，使［Ｐ］和［Ｖ］·［Ｖ－１］（条件数）极小化的问题，其中Ｐ是（Ａ＋ＢＦ）＇Ｐ＋Ｐ（Ａ＋ＢＦ）＝－２Ｉｎ的工定解，Ｖ是Ａ＋ＢＦ的特征向量矩阵．两种指标都反映了系统鲁棒稳定的程度．通过定义一矩阵函数并引入新的自由变量Ｕ，可放松极点配置的约束，并能系统的推导［Ｐ］／Ｕ及（［Ｖ］·［Ｖ－１］）／Ｕ，从而将鲁棒设计转化为无约束的梯度法寻优，实例说明，本文设计方法的效果很好．     

Molecular modeling benzo[a]pyrene N2-dG adducts in the two overlapping active sites of the Y-family DNA polymerase Dpo4

The potent, ubiquitous environmental mutagen/carcinogen benzo[a]pyrene (B[a]P) induces a single major adduct [+ta]-B[a]P-N2-dG, whose bypass in most cases results in either no mutation (dCTP insertion) or a G-->T mutation (dATP insertion). Translesion synthesis (TLS) of [+ta]-B[a]P-N2-dG generally requires DNA polymerases (DNAPs) in the Y-family, which exist in cells to bypass DNA damage caused by chemicals and radiation. A molecular dynamics (MD) study is described with dCTP opposite [+ta]-B[a]P-N2-dG in Dpo4, which is the best studied Y-family DNAP from a structural point of view. Two orientations of B[a]P-N2-dG (BPmi5 and BPmi3) are considered, along with two orientations of the dCTP (AS1 and AS2), as outlined next. Based on NMR studies, the pyrene moiety of B[a]P-N2-dG is in the minor groove, when paired with dC, and can point toward either the base on the 5'-side (BPmi5) or the 3'-side (BPmi3). Based on published X-ray structures, Dpo4 appears to have two partially overlapping active sites. The architecture of active site 1 (AS1) is similar to all other families of DNAPs (e.g., the shape of the dNTP). Active site 2 (AS2), however, is non-canonical (e.g., the beta- and gamma-phosphates in AS2 are approximately where the alpha- and beta-phosphates are in AS1). In the Dpo4 models generated herein, using the BPmi3 orientation the pyrene moiety of [+ta]-B[a]P-N2-dG points toward the duplex region of the DNA, and is accommodated without distortions in AS1, but with distortions in AS2. Considering the BPmi5 orientation, the pyrene moiety points toward the ss-region of DNA in Dpo4, and sits in a hole defined by the fingers and little fingers domain ("chimney"); BPmi5 is accommodated in AS2 without significant distortions, but poorly in AS1. In summary, when dCTP is paired with [+ta]-B[a]P-N2-dG in the two overlapping active sites in Dpo4, the pyrene in the BPmi3 orientation is accommodated better in active site 1 (AS1), while the pyrene in the BPmi5 orientation is accommodated better in AS2. Finally, we discuss why Y-family DNAPs might have two catalytic active sites.     

矢量汉字库生成算法的研究

本文发展了文献「１」的矢量汉字库生成算法，它可以解决原算法不能解决的孤立点以及仅由两点构成的直线段的处理问题。     

Efficient distributed algorithms for single-source shortest paths and related problems on plane networks

An efficient distributed algorithm is given for computing single-source shortest paths in an asynchronous planar network. The algorithm has message and time complexityO(pn) on ann-node network, wherep is the smallest number of faces needed to cover all the nodes, taken over all possible plane embeddings of the network. Each node has only local information about the network, consisting of an ordered list of its incident edges in the embedding that realizesp and the name of the covering face that it belongs to. The complexity of the algorithm ranges fromO(n) toO(n ²) asp ranges from 1 to Θ(n). The algorithm is more efficient than previous algorithms [A3], [F1] for a broad range of values forp; however, the algorithms in [A3] and [F1] do not require knowledge about the embedding. The single-source algorithm incorporates optimal distributed solutions to a number of interesting subproblems including: (i) decomposing the plane embedding into Θ(p) outerplane graphs with favorable properties; (ii) a single-source algorithm for outerplane graphs; and (iii) identifying any edge in an outerplane graph whose cost exceeds the distance between its endpoints. As an application, a communication-, time-, and space-efficient message-routing scheme is presented which adapts to changing link conditions and routes along near-shortest paths. This research was supported in part by a grant-in-aid of research from the Graduate School of the University of Minnesota. R. Janardan was also supported in part by NSF Grant CCR-8808574. Portions of this work were presented at the 4th International Workshop on Distributed Algorithms, Bari, Italy, September 1990.     

Mean analysis of an online algorithm for the vertex cover problem

In 2005, Demange and Paschos proposed in [M. Demange, V.Th. Paschos, On-line vertex-covering, Theoret. Comput. Sci. 332 (2005) 83-108] an online algorithm (noted LR here) for the classical vertex cover problem. They shown that, for any graph of maximum degree Δ, LR constructs a vertex cover whose size is at most Δ times the optimal one (this bound is tight in the worst case).Very recently, two of the present authors have shown in [F. Delbot, C. Laforest, A better list heuristic for vertex cover, Inform. Process. Lett. 107 (2008) 125-127] that LR has interesting properties (it is a good “list algorithm” and it can easily be distributed). In addition, LR has good experimental behavior in spite of its Δ approximation (or competitive) ratio and the fact that it can be executed without the knowledge of the full instance at the beginning.In this paper we analyze it deeper and we show that LR has good “average” performances: we prove that its mean approximation ratio is strictly less than 2 for any graph and is equal to 1+e−2≈1.13 in paths. LR is then a very interesting algorithm for constructing small vertex covers, despite its bad worst case behavior.     

Measure the quality level for a supplier-demand system by a multicommodity stochastic-flow network

From the point of view of quality management, it is important to meet the customer's demand. The probability that the system can satisfy the customer's demand is an important performance index, and can be used to measure the quality level of the system. In this paper, we use a multicommodity stochastic-flow network to describe the relationship between the supplier and the customer. Each node as well as each arc has several possible capacities and may fail. The network allows multiple types of commodities to be transmitted from the source to the sink. Given the demand for each commodity at the sink, evaluation of the probability that the system meets the demands is performed. Such a probability, named the system reliability, is a performance index of quality level. At first, a simple algorithm is proposed to generate all lower boundary points for the demand, and the system reliability can be calculated in terms of such points. The computational complexity of the proposed algorithm is polynomial time in number of arcs, nodes and minimal paths.