共查询到20条相似文献,搜索用时 316 毫秒
1.
RNA二级结构预测中动态规划的优化和有效并行 总被引:6,自引:0,他引:6
基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n4)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n2×k2)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n3)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比. 相似文献
2.
We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion–exclusion characterizations.
We show that the Exact Satisfiability problem of size l with m clauses can be solved in time 2
m
l
O(1) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number
of perfect matchings in an n-vertex graph in time 2
n
n
O(1) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732
n
) and exponential space.
We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover
instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most
three.
We extend the analysis to a number of related problems such as TSP and Chromatic Number. 相似文献
3.
We consider the problem of message (and bit) efficient
broadcasting in complete networks with dynamic faults. Despite the
simplicity of the setting, the problem turned out to be surprisingly
interesting from the algorithmic point of view.
In this paper we show an Ω(n + t
f
t/(t – 1)) lower bound on
the number of messages sent by any t-step broadcasting
algorithm, where f is the number of faults per step. The core of
the paper contains a constructive O(n + t
f
(t + 1)/t
) upper bound.
The algorithms involved are of time complexity O(t), not
strictly t.
In addition, we present a bit-efficient algorithm of O(n log2
n) bit and O(log n) time complexities. We also show that it is
possible to achieve the same message complexity even if the nodes
do not know the id’s of their neighbours, but instead have only a
Weak Sense of Direction. 相似文献
4.
We study the problem of scheduling unit execution time jobs with release dates and precedence constraints on two identical
processors. We say that a schedule is ideal if it minimizes both maximum and total completion time simultaneously. We give
an instance of the problem where the min-max completion time is exceeded in every preemptive schedule that minimizes total
completion time for that instance, even if the precedence constraints form an intree. This proves that ideal schedules do
not exist in general when preemptions are allowed. On the other hand, we prove that, when preemptions are not allowed, then
ideal schedules do exist for general precedence constraints, and we provide an algorithm for finding ideal schedules in O(n
3) time, where n is the number of jobs. In finding such ideal schedules we resolve a conjecture of Baptiste and Timkovsky (Math. Methods Oper.
Res. 60(1):145–153, 2004) Further, our algorithm for finding min-max completion-time schedules requires only O(n
3) time, while the most efficient solution to date has required O(n
9) time. 相似文献
5.
An integrative overview of the algorithmic characteristics of three well-known polynomialtime heuristics for the undirected Steiner minimum tree problem:shortest path heuristic (SPH),distance network heuristic (DNH), andaverage distance heuristic (ADH) is given. The performance of thesesingle-pass heuristics (and some variants) is compared and contrasted with several heuristics based onrepetitive applications of the SPH. It is shown that two of these repetitive SPH variants generate solutions that in general are better than solutions obtained by any single-pass heuristic. The worst-case time complexity of the two new variants isO(pn
3) andO(p
3
n
2), while the worst-case time complexity of the SPH, DNH, and ADH is respectivelyO(pn
2),O(m + n logn), andO(n
3) wherep is the number of vertices to be spanned,n is the total number of vertices, andm is the total number of edges. However, use of few simple tests is shown to provide large reductions of problem instances (both in terms of vertices and in term of edges). As a consequence, a substantial speed-up is obtained so that the repetitive variants are also competitive with respect to running times. 相似文献
6.
We present the first sublinear-time algorithms for computing order statistics in the Farey sequence and for the related problem
of ranking. Our algorithms achieve a running times of nearly O(n
2/3), which is a significant improvement over the previous algorithms taking time O(n).
We also initiate the study of a more general problem: counting primitive lattice points inside planar shapes. For rational
polygons containing the origin, we obtain a running time proportional to D
6/7, where D is the diameter of the polygon.
This work represents a merging of 19 and 21, with additional extensions. 相似文献
7.
We consider the problem of testing the roundness of manufactured disks
and balls using the finger probing model of Cole and Yap.
The running time of our procedures depends on the quality of
the object being considered. Quality is a parameter that is negative
when the object is not sufficiently round and positive when it is.
Quality values close to zero represent objects that are close to the
boundary between sufficiently round and insufficiently round.
When the object being tested is a disk and its center is known, we
describe a procedure that uses O(n) probes and O(n) computation
time. (Here n =| 1/q|, where q is the quality of the object.) When
the center of the object is not known, a procedure using O(n) probes
and O(n log n) computation time is described. When the object is a
ball, we describe a procedure that requires O(n2) probes and
O(n4) computation time. Lower bounds are also given that show
that these procedures are optimal in terms of the number of probes
used. These results extend previous results in two directions by
relaxing some of the assumptions required by previous results and by
extending these results for three-dimensional objects. 相似文献
8.
We present an algorithm to approximate edit distance between two ordered and rooted trees of bounded degree. In this algorithm,
each input tree is transformed into a string by computing the Euler string, where labels of some edges in the input trees
are modified so that structures of small subtrees are reflected to the labels. We show that the edit distance between trees
is at least 1/6 and at most O(n
3/4) of the edit distance between the transformed strings, where n is the maximum size of two input trees and we assume unit cost edit operations for both trees and strings. The algorithm
works in O(n
2) time since computation of edit distance and reconstruction of tree mapping from string alignment takes O(n
2) time though transformation itself can be done in O(n) time. 相似文献
9.
In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error
algorithm with updates and queries in O(n
ω(1,1,ε)−ε
) time given a lookahead of n
ε
operations, where ω(1,1,ε) is the exponent of multiplication of n×n matrix by n×n
ε
matrix. For ε≤0.294 we obtain an algorithm with queries and updates in O(n
2−ε
) time, whereas for ε=1 the time is O(n
ω−1). This is essentially optimal as it implies an O(n
ω
) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this
problem, we show an algorithm that requires
O(n\fracw2)O(n^{\frac{\omega}{2}})
time to process
n\frac12n^{\frac{1}{2}}
operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms
for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error.
All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest. 相似文献
10.
An Approximation Algorithm for the Minimum Co-Path Set Problem 总被引:1,自引:0,他引:1
We present an approximation algorithm for the problem of finding a minimum set of edges in a given graph G whose removal from G leaves a graph in which each connected component is a path. It achieves a ratio of
\frac 107\frac {10}{7}
and runs in O(n
1.5) time, where n is the number of vertices in the input graph. The previously best approximation algorithm for this problem achieves a ratio
of 2 and runs in O(n
2) time. 相似文献
11.
Xin He 《Algorithmica》1990,5(1):545-559
We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n
3/2) sequential time, orO(log4
n) parallel time withO(n3) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log3
n) time withO(n) processors on a PRAM. 相似文献
12.
Evolutionary trees describing the relationship for a set of species
are central in evolutionary biology, and quantifying differences
between evolutionary trees is therefore an important task. The
quartet distance is a distance measure between trees previously
proposed by Estabrook, McMorris, and Meacham. The quartet distance
between two unrooted evolutionary trees is the number of quartet
topology differences between the two trees, where a quartet topology
is the topological subtree induced by four species. In this paper
we present an algorithm for computing the quartet distance between
two unrooted evolutionary trees of n species, where all internal
nodes have degree three, in time O(n log n. The previous best
algorithm for the problem uses time O(n
2). 相似文献
13.
Takao Asano Tetsuo Asano Leonidas Guibas John Hershberger Hiroshi Imai 《Algorithmica》1986,1(1):49-63
Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n
2) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n
2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n
2) time, improving earlierO(n
2 logn) results. 相似文献
14.
Evolutionary trees describing the relationship for a set of species
are central in evolutionary biology, and quantifying differences
between evolutionary trees is therefore an important task. The
quartet distance is a distance measure between trees previously
proposed by Estabrook, McMorris, and Meacham. The quartet distance
between two unrooted evolutionary trees is the number of quartet
topology differences between the two trees, where a quartet topology
is the topological subtree induced by four species. In this paper
we present an algorithm for computing the quartet distance between
two unrooted evolutionary trees of n species, where all internal
nodes have degree three, in time O(n log n. The previous best
algorithm for the problem uses time O(n
2). 相似文献
15.
We consider the problem of fitting a step function to a set of points. More precisely, given an integer k and a set P of n points in the plane, our goal is to find a step function f with k steps that minimizes the maximum vertical distance between f and all the points in P. We first give an optimal Θ(nlog n) algorithm for the general case. In the special case where the points in P are given in sorted order according to their x-coordinates, we give an optimal Θ(n) time algorithm. Then, we show how to solve the weighted version of this problem in time O(nlog 4
n). Finally, we give an O(nh
2log n) algorithm for the case where h outliers are allowed. The running time of all our algorithms is independent of k. 相似文献
16.
Ak-extremal point set is a point set on the boundary of ak-sided rectilinear convex hull. Given ak-extremal point set of sizen, we present an algorithm that computes a rectilinear Steiner minimal tree in timeO(k
4
n). For constantk, this algorithm runs inO(n) time and is asymptotically optimal and, for arbitraryk, the algorithm is the fastest known for this problem. 相似文献
17.
We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n 3/2) sequential time, orO(log4 n) parallel time withO(n3) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log3 n) time withO(n) processors on a PRAM.
相似文献18.
分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n2)处理器,时间复杂度为O(log2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n3)处理器,计算时间复杂度为O(logn). 相似文献
19.
Sanguthevar Rajasekaran David S.L. Wei 《Journal of Parallel and Distributed Computing》1997,41(2):1771
We consider the problems of selection, routing, and sorting on ann-star graph (withn! nodes), an interconnection network which has been proven to possess many special properties. We identify a tree like subgraph (which we call a “(k, 1,k) chain network”) of the star graph which enables us to design efficient algorithms for the above mentioned problems. We present an algorithm that performs a sequence ofnprefix computations inO(n2) time. This algorithm is used as a subroutine in our other algorithms. We also show that sorting can be performed on then-star graph in timeO(n3) and that selection of a set of uniformly distributednkeys can be performed inO(n2) time with high probability. Finally, we also present a deterministic (nonoblivious) routing algorithm that realizes any permutation inO(n3) steps on then-star graph. There exists an algorithm in the literature that can perform a single prefix computation inO(nlgn) time. The best-known previous algorithm for sorting has a run time ofO(n3lgn) and is deterministic. To our knowledge, the problem of selection has not been considered before on the star graph. 相似文献
20.
Fábio Protti Maise Dantas da Silva Jayme Luiz Szwarcfiter 《Theory of Computing Systems》2009,44(1):91-104
A graph G is said to be a bicluster graph if G is a disjoint union of bicliques (complete bipartite subgraphs), and a cluster graph if G is a disjoint union of cliques (complete subgraphs). In this work, we study the parameterized versions of the NP-hard Bicluster Graph Editing and Cluster Graph Editing problems. The former consists of obtaining a bicluster graph by making the minimum number of modifications in the edge set
of an input bipartite graph. When at most k modifications are allowed (Bicluster(k) Graph Editing problem), this problem is FPT, and can be solved in O(4
k
nm) time by a standard search tree algorithm. We develop an algorithm of time complexity O(4
k
+n+m), which uses a strategy based on modular decomposition techniques; we slightly generalize the original problem as the input
graph is not necessarily bipartite. The algorithm first builds a problem kernel with O(k
2) vertices in O(n+m) time, and then applies a bounded search tree. We also show how this strategy based on modular decomposition leads to a new
way of obtaining a problem kernel with O(k
2) vertices for the Cluster(k) Graph Editing problem, in O(n+m) time. This problem consists of obtaining a cluster graph by modifying at most k edges in an input graph. A previous FPT algorithm of time O(1.92
k
+n
3) for this problem was presented by Gramm et al. (Theory Comput. Syst. 38(4), 373–392, 2005, Algorithmica 39(4), 321–347, 2004). In their solution, a problem kernel with O(k
2) vertices is built in O(n
3) time. 相似文献