A mildly exponential approximation algorithm for the permanent

A new approximation algorithm for the permanent of ann ×n 0,1-matrix is presented. The algorithm is shown to have worst-case time complexity exp(O(n ^1/2 log² n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity exp((n)).Supported by SERC Grant GR/F 90363; work done in part while visiting DIMACS (Center for Discrete Mathematics and Computer Science).Supported by an NSF PYI grant, with matching equipment grant from the AT&T Foundation; work done in part while visiting DIMACS.     

Antimagic labeling and canonical decomposition of graphs

An antimagic labeling of a connected graph with m edges is an injective assignment of labels from {1,…,m} to the edges such that the sums of incident labels are distinct at distinct vertices. Hartsfield and Ringel conjectured that every connected graph other than K₂ has an antimagic labeling. We prove this for the classes of split graphs and graphs decomposable under the canonical decomposition introduced by Tyshkevich. As a consequence, we provide a sufficient condition on graph degree sequences to guarantee an antimagic labeling.     

Discrete particle swarm optimization based on estimation of distribution for terminal assignment problems

Terminal assignment problem (TEAP) is to determine minimum cost links to form a network by connecting a given set of terminals to a given collection of concentrators. This paper presents a novel discrete particle swarm optimization (PSO) based on estimation of distribution (EDA), named DPSO-EDA, for TEAP. EDAs sample new solutions from a probability model which characterizes the distribution of promising solutions in the search space at each generation. The DPSO-EDA incorporates the global statistical information collected from personal best solutions of all particles into the PSO, and therefore each particle has comprehensive learning and search ability. In the DPSO-EDA, a modified constraint handling method based on Hopfield neural network (HNN) is also introduced to fit nicely into the framework of the PSO and thus utilize the merit of the PSO. The DPSO-EDA adopts the asynchronous updating scheme. Further, the DPSO-EDA is applied to a problem directly related to TEAP, the task assignment problem (TAAP), in order to show that the DPSO-EDA can be generalized to other related combinatorial optimization problems. Simulation results on several problem instances show that the DPSO-EDA is better than previous methods.     

Tabu search-based metaheuristic algorithm for software system reliability problems

This paper presents a new metaheuristic-based algorithm for complex reliability problems. The algorithm effectively uses features of the Tabu Search paradigm, with special emphasis on the exploitation of memory-based mechanisms. It balances intensification with diversification via the use of short-term and long-term memory. The algorithm has been thoroughly tested on benchmark problems from the literature as well as on a pool of random generated instances of very large scale software systems. The proposed algorithm proves to be robust with respect to its parameters and it is especially suited for very large scale instances of the reliability problem, when exact approaches are doomed to fail.     

改进的Sunday模式匹配算法

在基于模式匹配的检测方法中,匹配效率是检测技术的瓶颈,间接影响入侵检测系统的实时性能。该文对4种模式匹配算法进行分析后,选择最优的Sunday算法进行改进。该算法进行匹配前先找到模式串中的特征字符（出现概率最小的字符）,进行特征字符与尾字符双重匹配,失败则移动尽可能远的距离。实验结果证明匹配效率比Sunday算法有一定的提高。     

具有计算可靠性的符号模型

MW方法仅考虑使用公钥加密原语,不包含{{mk}k类型消息的双方协议。针对该问题,使用公钥加密和对称加密,建立扩展标记符号模型与扩展计算模型,论证扩展标记符号模型的计算可靠性,实现对MW方法的扩展。     

并行计算模型参数动态分析软件包设计

并行计算模型的发展引入越来越多的模型参数。对并行计算模型参数动态采集分析软件包DEMPAT的整体框架进行研究,实现基于硬件性能计数器的存储层次参数采集模块。实验表明,该模块能够准确快速地获取存储层次参数且具有较好的可移植性。     

Group path covering and distance two labeling of graphs

For a positive integer d, an L(d,1)-labeling f of a graph G is an assignment of integers to the vertices of G such that |f(u)−f(v)|?d if uv∈E(G), and |f(u)−f(v)|?1 if u and u are at distance two. The span of an L(d,1)-labeling f of a graph is the absolute difference between the maximum and minimum integers used by f. The L(d,1)-labeling number of G, denoted by λd,1(G), is the minimum span over all L(d,1)-labelings of G. An L^′(d,1)-labeling of a graph G is an L(d,1)-labeling of G which assigns different labels to different vertices. Denote by the L^′(d,1)-labeling number of G. Georges et al. [Discrete Math. 135 (1994) 103-111] established relationship between the L(2,1)-labeling number of a graph G and the path covering number of Gc, the complement of G. In this paper we first generalize the concept of the path covering of a graph to the t-group path covering. Then we establish the relationship between the L^′(d,1)-labeling number of a graph G and the (d−1)-group path covering number of Gc. Using this result, we prove that and for bipartite graphs G can be computed in polynomial time.     

Δ3-1,2,4—噻二唑类化合物的量子化学及构效关系研究

Δ3-1,2,4—噻二唑类化合物具有抑制黄瓜霜霉病毒的杀菌活性。本文用半经验PM3方法对25个该类化合物进行了量子化学计算,并依据原子的净电荷、前沿轨道能级、轨道主要成分及原子在前沿轨道中所占比重等计算结果和多重回归分析讨论了该类化合物的活性部位,为该类化合物结构与活性的研究奠定了理论基础。