共查询到20条相似文献,搜索用时 0 毫秒
1.
《Journal of Parallel and Distributed Computing》1994,20(1):43-55
We present a parallel algorithm for finding minimum cutsets in reducible graphs. For a reducible graph that has N nodes our algorithm runs in O(log3N) time using O(N3/log N) PEs on the EREW P-RAM model of computation. We also present a parallel heuristic for finding minimal cutsets in general graphs. 相似文献
2.
3.
The distance between at least two vertices becomes longer after the removal of a hinge vertex. Thus a faulty hinge vertex
will increase the overall communication cost in a network. Therefore, finding the set of all hinge vertices in a graph can
be used to identify critical nodes in a real network. An O(n log n) time algorithm has been proposed here to find all hinge vertices of a trapezoid graph with n vertices. 相似文献
4.
《Journal of Parallel and Distributed Computing》1998,52(1):96-108
TheP4-tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few inducedP4(cographs,P4-sparse graphs,P4-lite graphs). Here, we propose an extension of R. Lin and S. Olariu's work (1994.J. Parallel Distributed Computing22, 26–36.) on cographs, using the modular decomposition. As an application, we show how to obtain a maximum matching parallel algorithm for the family ofP4-tidy graphs (repre- sented by a parse tree) inO(log n) time withO(n/log n) processors in the EREW-PRAM model withn-vertex graphs. 相似文献
5.
6.
本文通过对网络及网络最大流问题的符号代数判定图(ADD)描述,将网络中的结点和边用ADD隐式表示,并利用Gabow的容量变尺度算法的主要思想,将一般网络最大流问题化为一系列的单位容量网络最大流问题,结合Hachtel等的单位容量网络最大流问题的求解算法,给出了网络最大流问题求解的符号ADD增广路径算法,简称为符号ADD算法.与Dinic算法、Karzanov算法相比,本文算法的空间复杂度得到了改善.实验结果表明,本文算法是切实有效的,且可处理更大规模的问题. 相似文献
7.
从互联网海量信息中快速准确地获取有效的信息变得非常重要。依据用户间信任关系给出推荐是一种非常有效的快速获取信息的方法,然而用户间信任关系通常非常的稀疏,很难为用户找到合适的信任关系,极大地影响了推荐效果。提出将扩展用户信任关系的过程转化成求解用户间信任最大流的问题,通过求解用户集合中的最大流得到用户信任关系。在Epinions数据集上的实验结果表明,基于最大流求解的信任关系给出的推荐比基于概率的矩阵分解、社会推荐、基于信任和不信任推荐方法有更好的效果。 相似文献
8.
9.
网络最大流问题是图论中的经典问题之一,对于最大流问题有很多经典的算法,但这些经典算法皆有不足之处。针对其不足,文中通过引入容量差的概念,对算法进行了一些改进。改进算法的原则是优先选择路径最短且容量差最大的路径进行增广,若当路径长度一样并且容量差也一样时就要对其修正,然后选择修正后的路径,这样每次增广至少使一条弧达到饱和。通过实例说明了改进算法的可行性,整个运算过程可以在一个图上完成,直观性强并且方便计算,较传统算法更为有效。 相似文献
10.
11.
A cycle cover of a graph is a spanning subgraph, each node of which is part of exactly one simple cycle. A k-cycle cover is a cycle cover where each cycle has length at least k. Given a complete directed graph with edge weights zero and one, Max-k-DDC(0,1) is the problem of finding a k-cycle cover with maximum weight. We present a 2/3 approximation algorithm for Max-k-DDC(0,1) with running time O(n 5/2). This algorithm yields a 4/3 approximation algorithm for Max-k-DDC(1,2) as well. Instances of the latter problem are complete directed graphs with edge weights one and two. The goal is to find a k-cycle cover with minimum weight. We particularly obtain a 2/3 approximation algorithm for the asymmetric maximum traveling salesman problem with distances zero and one and a 4/3 approximation algorithm for the asymmetric minimum traveling salesman problem with distances one and two. As a lower bound, we prove that Max-k-DDC(0,1) for k 3 and Max-k-UCC(0,1) (finding maximum weight cycle covers
in undirected graphs) for k 7 are \APX-complete. 相似文献
12.
13.
针对变分光流法无法有效检测由间断、遮挡等因素造成的错误光流分量的缺陷,提出一种基于PSO(Particle Swarm Optimization)的光流算法。该方法在Classic+NL算法模型的基础上计算出光流后,引入前向光流和后向光流的运动一致性理论来判断遮挡区域,并通过基于PSO的修补法来实现对遮挡区域错误光流的有效修补,同时,利用邻域光流修补法实现了再次修补。实验结果表明,该方法能有效克服由间断、遮挡等因素造成的错误光流分量的缺陷,更准确地刻画出光流,提高光流的计算精度。 相似文献
14.
一个基于模型的故障诊断算法 总被引:1,自引:0,他引:1
基于模型的诊断方法是重要的故障诊断方法之一,本文首先分析了现有的基于模型的故障诊断的优缺点,指出了这些方法的不足之处,然后再对这些方法进行了改进。因为求诊断问题是针对受限语言的,所以我们只求受限语言的质蕴含项,并且在算法中增加了极小性检查,以确保得到的结论都是质蕴含项,在此基础上给出了一个基于模型的诊断算法。 相似文献
15.
已有的Join任务图的调度算法大多不是基于通信竞争的环境而开发,且未考虑节省处理机的问题,使算法的应用效果不佳.因此,针对Join任务图,提出一个通信竞争环境的调度算法,该算法因串行通信边而改善其调度效率,时间复杂度为O(vlogv),其中,v为图中任务的个数.实验结果表明,与其他算法相比,该算法的调度长度较短且使用的... 相似文献
16.
基于信息熵的核属性增量式高效更新算法 总被引:1,自引:0,他引:1
针对基于信息熵求核算法效率不理想的情况,给出信息观下的二进制差别矩阵定义,理论上证明基于信息熵的核属性与基于二进制差别矩阵的核属性等价;并将决策表划分为相容的对象集和不相容的对象集,缩小求核算法的搜索空间;然后针对动态的决策表,研究核属性的增量更新机制,由此构造一种基于信息熵的核属性增量式高效更新算法。实例分析与实验结果验证文中算法优于同类求解算法。 相似文献
17.
For a rotator graph with n! nodes, Hsu and Lin [C.C. Hsu, H.R. Lin, H.C. Chang, K.K. Lin, Feedback Vertex Sets in Rotator Graphs, in: Lecture Notes in Comput. Sci., vol. 3984, 2006, pp. 158-164] first proposed an algorithm which constructed a feedback vertex set (FVS) with time complexity O(nn−3). In addition, they found that the size of the FVS is n!/3, which was proved to be minimum. In this paper, we present an efficient algorithm which constructs an FVS for a rotator graph in O(n!) time and also obtains the minimum FVS size n!/3. In other words, this algorithm derives the optimal result with linear time complexity in terms of the number of nodes in the rotator graph. 相似文献
18.
该研究为Hamilton环路(道路)问题设计出了一个多项式时间算法,论证了它的正确性。根据该算法编制了程序,进行了大量的实例计算。文章公布了主要研究方法、过程、实验数据,以及粗略的算法步骤。详细的算法步骤和证明将在随后的论文中发表。由于Hamilton环路(道路)为著名的NP完全问题,而作者认为自己已彻底解决了NP复杂问题。 相似文献
19.
给出一种求解网络最大流的新算法,该算法是针对增广链选取的顺序不当而无法得到理想的最大流,且在计算过程中每步都需要画一个网络图等问题进行的改进。利用分层及度差的概念,在选择增广链时优先选择路径最短且度差较大的路径,相同层次度差相同时优先选择容差较大的路径,在饱和的弧上画上终止符。最后用实例进行了验证并和Ford—Fulkerson算法做了比较,体现了它的高效性,避免了标号,且只需要在一个图上即可完成。整个运算过程直观性强,计算方便。 相似文献
20.
This paper considers the problem of scheduling n independent jobs in g-stage hybrid flow shop
environment. To address the realistic assumptions of the proposed problem, two additional traits
were added to the scheduling problem. These include setup times, and the consideration of maximum
completion time together with total tardiness as objective function. The problem is to determine
a schedule that minimizes a convex combination of objectives. A procedure based on hybrid the
simulated annealing; genetic algorithm and local search so-called HSA-GA-LS are proposed to handle
this problem approximately. The performance of the proposed algorithm is compared with a genetic
algorithm proposed in the literature on a set of test problems. Several performance measures are
applied to evaluate the effectiveness and efficiency of the proposed algorithm in finding a good quality
schedule. From the results obtained, it can be seen that the proposed method is efficient and effective. 相似文献