共查询到17条相似文献,搜索用时 140 毫秒
1.
将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义. 相似文献
2.
模糊聚类计算的最佳算法 总被引:14,自引:0,他引:14
给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n2).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n3logn)计算时间相比,新算法至少降低了O(n相似文献
3.
4.
5.
6.
RNA二级结构预测中动态规划的优化和有效并行 总被引:6,自引:0,他引:6
基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n4)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n2×k2)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n3)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比. 相似文献
7.
分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n2)处理器,时间复杂度为O(log2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n3)处理器,计算时间复杂度为O(logn). 相似文献
8.
布尔可满足性问题(SAT)是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题(k-SAT),从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O((2-2/k)n),当k=3时,最好算法时间复杂度为O(1.308n).而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题(3-RSSAT),证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O(1.890n)判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O(1.890n)精确算法,该算法与子句长度无关. 相似文献
9.
10.
一种高效频繁子图挖掘算法 总被引:11,自引:1,他引:11
由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题--频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O(n3·2n),其中,n是图集中的频繁边数.提出算法的时间复杂性是O〔2n·n2.5/logn〕,性能提高了O(√n·logn)倍.实验结果也证实了这一理论分析. 相似文献
11.
《Journal of Parallel and Distributed Computing》2004,64(5):649-661
Checkpointing with rollback recovery is a well-known method for achieving fault-tolerance in distributed systems. In this work, we introduce algorithms for checkpointing and rollback recovery on asynchronous unidirectional and bi-directional ring networks. The proposed checkpointing algorithms can handle multiple concurrent initiations by different processes. While taking checkpoints, processes do not have to take into consideration any application message dependency. The synchronization is achieved by passing control messages among the processes. Application messages are acknowledged. Each process maintains a list of unacknowledged messages. Here we use a logical checkpoint, which is a standard checkpoint (i.e., snapshot of the process) plus a list of messages that have been sent by this process but are unacknowledged at the time of taking the checkpoint. The worst case message complexity of the proposed checkpointing algorithm is O(kn) when k initiators initiate concurrently. The time complexity is O(n). For the recovery algorithm, time and message complexities are both O(n). 相似文献
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.
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). 相似文献
14.
Distance labeling schemes are composed of a marker algorithm for
labeling the vertices of a graph with short labels, coupled with a
decoder algorithm allowing one to compute the distance between
any two vertices directly from their labels (without using any additional
information).
As applications for distance labeling schemes
concern mainly large and dynamically changing networks,
it is of interest to study distributed dynamic labeling schemes.
The current paper considers the problem on dynamic trees,
and proposes efficient distributed schemes for it.
The paper first presents a labeling scheme for distances in the dynamic
tree model, with amortized message complexity O(log2
n) per operation,
where n is the size of the tree at the time the operation takes place.
The protocol maintains O(log2
n) bit labels.
This label size is known to be optimal even in the static scenario.
A more general labeling scheme is then introduced for the dynamic tree
model, based on extending an existing static tree labeling
scheme to the dynamic setting. The approach fits a number of
natural tree functions, such as distance, separation level, and flow.
The main resulting scheme incurs an overhead
of an O(log n) multiplicative factor in both the label size and
amortized message complexity in the case of dynamically growing
trees (with no vertex deletions).
If an upper bound on n is known in advance,
this method yields a different tradeoff, with an
O(log2
n/log log n) multiplicative overhead on the label
size but only an O(log n/log log n) overhead on the amortized
message complexity.
In the fully dynamic model the scheme also incurs an increased
additive overhead in amortized communication, of O(log2
n)
messages per operation. 相似文献
15.
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. 相似文献
16.
To maintain high reliability and availability, system-level diagnosis should be considered for the multiprocessor systems. The self-diagnosis problem of hypermesh, emerging potential optical interconnection networks for multiprocessor systems, is solved in this paper. We derive that the precise one-step diagnosability of kn-hypermesh is n(k − 1). Based on the principle of cycle decomposition, a one-step t-fault diagnosis algorithm for kn-hypermesh which runs in O(knn(k − 1)) time also is described. 相似文献
17.
We present in this paper three deterministic broadcast and a gossiping algorithm suitable for ad hoc networks where topology
changes range from infrequent to very frequent. The proposed algorithms are designed to work in networks where the mobile
nodes possessing collision detection capabilities. Our first broadcast algorithm accomplishes broadcast in O(nlog n) for networks where topology changes are infrequent. We also present an O(nlog n) worst case time broadcast algorithms that is resilient to mobility. For networks where topology changes are frequent, we
present a third algorithm that accomplishes broadcast in O(Δ·nlog n + n·|M|) in the worst case scenario, where |M| is the length of the message to be broadcasted and Δ the maximum node degree. We then extend one of our broadcast algorithms
to develop an O(Dn log n + D2) algorithm for gossiping in the same network model. 相似文献