基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

枚举有符号基因组的可行交互移位算法

交互移位排序问题(SRT)是寻找一个使一个基因组转变为另一个基因组的最短交互移位序列。现在已有多个多项式时间的SRT算法,但大多数问题实例都有许多个最短交互移位序列,因此寻找所有最短交互移位序列问题是SRT一个自然的推广。这个问题可以归约为寻找一个基因组相对于另一个基因组的全部可行交互移位,即所有移位ρ满足:在一个基因组上执行ρ之后,所得基因组相对于另一个基因组的移位距离会减少。本文提出一个用来寻找全部可行交互移位的有效算法,尽管新算法的时间复杂度比穷举法改进不大,但实验结果表明,其在实际运行中表现更好。     

一种节省空间的排序算法

目前报道的一些排序算法，空间复杂度都比较大．提出了一种改进其空间复杂度的方法，其特点是算法简单、稳定，时间复杂度为O(n^2)，空间复杂度为2n，达到下界．与传统的排序算法用变量与变量比较的思路不同，本文提出的是一种用变量与其分布区间进行比较的新思路．本算法特别适合那些范围确定且分布基本均匀的待排数据，也适合一般数据对象的排序．     

位排序--一种快速排序法

众所周知,排序速度的快慢,取决于排序算法的时间复杂度和空间复杂度。因而,排序算法设计的主导思想,就是要千方百计降低算法的时间复杂度和空间复杂度。虽然计算机硬件的运算速度越来越快,但排序算法的研究仍是算法理论中的一个重要课题。已有的排序算法很多,在所有基于“记录关键字之间比较”的排序方法中,快速排序(quick sort)是平均时间性能最好的一种方法,平均时间为O（n*log n)。但是在最坏情况下,时间复杂度却很高,为O(n^2)。     

中值滤波编码算法的设计原理与实现

介绍了一种中值滤波编码快速算法的设计思路、基本运算步骤、算法流程及算法分析．该算法利用数据窗口中元素的位置关系，并考虑了相邻的两个中值滤波窗口内数据元素的相关性，采用编码排序的方法保留前面窗口内数据的编码排序信息，作为后一个窗口内数据排序的参考依据．由此，将传统算法中相邻的两次中值滤波运算合并为一次进行，减少了中值滤波过程中比较运算的次数．该算法可将传统算法的复杂度O(n^2)简化为O(n)．     

基于实时逻辑的时间约束检测方法

本文针对具有严格时间要求的系统,阐述并分析了三种利用实时逻辑实现时间约束检测的方法。第一种方法通过检测系统规范和安全性断言的一致性来验证约束的满足性,非常适合于系统规范的设计与可满足性检测,算法的时间复杂度是O(n^2) O(n^2) O(2^k)。第二种方法利用实时逻辑与约束图的方法实现运行时的时间约束检测,但检测时的系统约束条件不够第三种方法简约,算法时间复杂度为O(n^2),改进之后为O(n^2)。第三种方法通过对约束图的处理,减少运行时系统检测的约束条件,从而减少运行时的时间约束条件的搜索时间,算法的时间复杂度为O(n),在实时性和检测效率明显优于前两种方法。但需要运行前优化约束规则,将会增加额外的时间和空间复杂度。     

一种判定图中Hamilton圈的邻接边增长算法

一个图是否为Hamilton图在于图中是否有Hamilton圈。文中提出了变换的方法来寻找图中的Hamilton圈，即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈。由此，设计了一个在Edmonds意义下的有效算法——自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换，证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n^2)。最后通过应用实例说明该算法的有效性和实用性。     

改进的赫夫曼树（Huffman Tree）和赫夫曼编码（Huffman Code）构造算法

通过将待排序的数据应用快速排序算法进行排序处理,使得赫夫曼算法（Huffman Algorithm）65时间复杂度从O（n^2）降低为O（n＊log2n）。当用于构造赫夫曼树（Huffman Tree）的结点比较多时,可较大的提高程序的运行时间。     

循环插入排序法

文章提出了一种循环插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了一类时间复杂度为O(N2)排序法的时间复杂度,其实用价值是该排序法在一类时间复杂度为O(N2)排序法中排序效率较高的,其平均排序速度比直接插入排序法、选择排序法、冒泡排序快50%～63%。     

4路插入排序法

提出一种4路插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了一类时间复杂度为O（N^2）排序法的时间复杂度，其实用价值是该排序法存一类时间复杂度为O（N^2）排序法中排序效率较高的，其平均排序速度比直接插入排序法、选择排序法、冒泡排序快66％以上。     

A new linear time algorithm to compute the genomic distance via the double cut and join distance

The genomic distance problem in the Hannenhalli–Pevzner (HP) theory is the following: Given two genomes whose chromosomes are linear, calculate the minimum number of translocations, fusions, fissions and inversions that transform one genome into the other. This paper presents a new distance formula based on a simple tree structure that captures all the delicate features of this problem in a unifying way, and a linear time algorithm for computing this distance.     

低度图的最大团求解算法

在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d)。给出一种求解低度图的最大团的确定性算法。该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题。算法时间复杂度为O(d•n3)。其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m。     

骨粒串主导的自由曲面变形算法

由于目前广泛应用的骨骼子空间变形算法本身固有的缺陷，常常导致生成的曲面出现“塌陷”与“萎缩”，严重影响了生成曲面的真实感．提出一种骨粒串主导的自由曲面变形算法，通过重构曲面模型，将骨骼与曲面相结合，并把虚拟的骨骼实体化，成为可变形的骨粒串．变形时先计算每一骨粒的新坐标，然后计算相应皮肤顶点的新坐标．实验结果表明，该算法有效地消除了“塌陷”与“萎缩”，生成的曲面具有高度真实感．     

Distortion-Free Steganography for Polygonal Meshes

We present a technique for steganography in polygonal meshes. Our method hides a message in the indexed rep‐resentation of a mesh by permuting the order in which faces and vertices are stored. The permutation is relative to a reference ordering that encoder and decoder derive from the mesh connectivity in a consistent manner. Our method is distortion‐free because it does not modify the geometry of the mesh. Compared to previous steganographic methods for polygonal meshes our capacity is up to an order of magnitude better. Our steganography algorithm is universal and can be used instead of the standard permutation steganography algorithm on arbitrary datasets. The standard algorithm runs in Ω (n² log² n log log n) time and achieves optimal O(nlog n) bit capacity on datasets with n elements. In contrast, our algorithm runs in O(n) time, achieves a capacity that is only one bit per element less than optimal, and is extremely simple to implement.     

New fast parallel algorithm for the connected component problem and its VLSI implementation

We present an O(log n) compare-exchange time parallel algorithm to compute the connected components of a given graph. We also introduce a simple regular VLSI architecture on which the proposed algorithm can readily be implemented requiring n³ identical processing elements and O(n) communication time, where n is the number of vertices in the graph.     

A 2-approximation algorithm for genome rearrangements by reversals and transpositions

Recently, a new approach to analyze genomes evolving which is based on comparision of gene orders versus traditional comparision of DNA sequences was proposed (Sankoff et al. 1992). The approach is based on the global rearrangements (e.g., inversions and transpositions of fragments). Analysis of genomes evolving by inversions and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, i.e., sorting of a permutation using reversals and transpositions of arbitrary fragments. We study sorting of signed permutations by reversals and transpositions, a problem which adequately models genome rearrangements, as the genes in DNA are oriented. We establish a lower bound and give a 2-approximation algorithm for the problem.     

A new algorithm to compute vertex cutsets in a graph

A new efficient algorithm has been presented in this paper to compute all the vertex cutsets between two specified vertices in a given symmetric graph. The algorithm has been developed into two distinct phases, i.e. in the first phase all the proper flow paths between the two specified vertices are generated, and in the second phase the vertex cutsets are determined from the information of the proper flow paths. The proposed algorithm seems to be economical in terms of computation time and it offers easy programmability on a digital computer.     

Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs

This paper presents an optimal sequential and an optimal parallel algorithm to compute a minimum cardinality Steiner set and a Steiner tree. The sequential algorithm takes O ( n ) time and parallel algorithm takes O (log n ) time and O ( n /log n ) processors on an EREW PRAM model.