线性连续系统模型离散化的递推算法

利用简单的数学工具实现了线性连续时间系统向离用时间系统的转换。算法既避免了矩阵的求逆运算，又可同时获得系统的脉冲传递函数，也可用于离散状态方程时的求解。仿真结果表明，所得结果对于连续时间系统的计算机仿真分析和控制是有效的。     

A Linear Time Algorithm for Sequential Diagnosis in Hypercubes

This paper describes a new sequential diagnosis algorithm for hypercubes. The algorithm is based on the PMC model and it assumes the existence of a central observer for syndrome decoding. If we denote the total number of processors in a given hypercube by N, then the algorithm achieves Θ([formula]) degree of diagnosability using only O(N) tests over all iterations of diagnosis and repair. The aggregated syndrome decoding time is also shown to be O(N) for this algorithm. The number of iterations of diagnosis and repair needed by the algorithm is O(log N).     

Optimal Edge Ranking of Trees in Linear Time

Given a tree, finding an optimal node ranking and finding an optimal edge ranking are interesting computational problems. The former problem already has a linear time algorithm in the literature. For the latter, only recently polynomial time algorithms have been revealed, and the best known algorithm requires more than quadratic time. In this paper we present a new approach for finding an optimal edge ranking of a tree, improving the time complexity to linear. Received April 22, 1998; revised November 19, 1998.     

Exact Algorithms for <Emphasis Type="Italic">L</Emphasis>(2,1)-Labeling of Graphs

The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,…,k} is an L(2,1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k≥4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O ^*((k+1) ⁿ ) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k=4, where the running time of our algorithm is O(1.3006 ⁿ ). Furthermore we show that dynamic programming can be used to establish an O(3.8730 ⁿ ) algorithm to compute an optimal L(2,1)-labeling.     

A Linear Time Lower Bound on McCreight and General Updating Algorithms for Suffix Trees

Suffix trees are the fundamental data structure of combinatorial pattern matching on words. Suffix trees have been used in order to give optimal solutions to a great variety of problems on static words, but for practical situations, such as in a text editor, where the incremental changes of the text make dynamic updating of the corresponding suffix trees necessary, this data structure alone has not been used with success. We prove that, for dynamic modifications of order O(1) of words of length n, any suffix tree updating algorithm, such as the ones proposed by McCreight, requires O(n) worst-case running time, as for the full reconstruction of the suffix tree. Consequently, we argue that this data structure alone is not appropriate for the solution of combinatorial problems on words that change dynamically.     

一个关于Hamilton环（路）的多项式时间算法

该研究为Hamilton环路（道路）问题设计出了一个多项式时间算法,论证了它的正确性。根据该算法编制了程序,进行了大量的实例计算。文章公布了主要研究方法、过程、实验数据,以及粗略的算法步骤。详细的算法步骤和证明将在随后的论文中发表。由于Hamilton环路（道路）为著名的NP完全问题,而作者认为自己已彻底解决了NP复杂问题。     

计算一类有向网络可靠性的线性时间算法

该文使用的可靠性保护缩减的方法计算有向网络ST可靠性（存在从源点到汇点正常运行道路的概率）是计算网络可靠性的常用方法之一,而且人们非常关心怎样的网络计算其可靠性存在线性时间算法,作者提出了两类新的可靠性保护缩减－－源桥缩减和惠斯通桥缩减和一类有向无圈网络,称之为WST网络,该类网络是对以前的BSP网络的扩展并且对于该类网络提出了一个计算其可靠性的线性时间算法。     

计算一类网络K--终点可靠性的线性时间算法

可靠性保护缩减的方法是计算网络可靠性的常用手段之一，而且关心哪类网络的可靠性存在线性时间算法．给出了一类新的可靠性保护缩减-桥缩减和一类无向网络，称之为WST网络，该类网络是对串并联网络的扩展并且对该类网络提出了一个计算K-终点可靠性的线性时间算法，其算法复杂性为O(|E|^2)．     

一个新的二叉树的轮廓线索树构造算法

本文给出了二叉树的轮廓线索树的一个新的构造算法 .与 Reingdd的算法相比 ,该算法简单、高效、便于分析 ,易于推广到 m-叉树的轮廓线索树的构造算法上     

离散时间线性系统最优控制的遗传算法实现

本文提出了求解控制变量受区间约束情形的离散时间线性系统最优控制的遗传算法,在遗传算法框架下给出了离散时间线性系统最优控制问题可行解的编码及初始化方法,设计了选择、交叉、变异等遗传算子,并对初始化方法及各种遗传算子的可行性给出理论分析。     

线性时间检测器生成算法的改进

针对基于人工免疫的网络入侵检测中的线性时间检测器生成算法生成的检测器存在冗余以及时问和空间代价与r呈指数关系，算法开销受r的影响较大的不足，对其进行了改进，采用了去除冗余检测器以及分割字符串的改进算法来生成检测器，通过实验证明了算法的有效性。     

线性时间选择算法时间复杂度深入研究

算法研究是计算机科学的核心领域之一。文中针对元素选择问题及解此问题的线性时间选择算法进行了深入研究,详细分析并论证了期望情况下与最坏情况下线性时间选择算法的时间复杂度,并对拟中位数元素选择问题进行了深层次的拓展,通过计算比较求出了线性时间下的最小复杂度因子。以期有助于该算法在相关领域的应用。     

A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree Network

In a model of facility location problem, the uncertainty in the weight of a vertex is represented by an interval of weights, and the objective is to minimize the maximum “regret.” The most efficient algorithm previously known for finding the minmax regret 1-median in a tree network with nonnegative vertex weights takes O(nlogn) time. We improve it to O(n), settling the open problem posed by Brodal et al. (Oper. Res. Lett. 36:14–18, 2008).     

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs

Given a graph G=(V,E) and two vertices s,t ∈ V , s\neq t , the Menger problem is to find a maximum number of disjoint paths connecting s and t . Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively. For planar graphs the edge disjoint Menger problem has been solved to optimality [W2], while the fastest algorithm for the arc disjoint version is Weihe's general maximum flow algorithm for planar networks [W1], which has running time \bf O (|V| log |V|) . Here we present a linear time, i.e., asymptotically optimal, algorithm for the arc disjoint version in planar directed graphs. Received August 1997; revised January 1999.     

A Distributed Algorithm for Constructing Minimal Spanning Trees

Most algorithms for constructing minimal spanning trees are sequential in operation. Distributed algorithms for constructing these trees operate both concurrently and asynchronously, and are useful in store-and-forward packet-switching computer-communication networks where there is typically no single source of control. The difficulties in designing such algorithms arise from communication and synchronization problems. This paper discusses these problems and describes the first distributed algorithm for constructing minimal spanning trees. This algorithm and the principles and techniques underlying its design will find application in large communication networks and large multiprocessor computer systems.