| 求解图最大团的并行算法 |
| |
| 引用本文： | 马军,马绍汉.求解图最大团的并行算法[J].山东大学学报(理学版),1990(3). |
| |
| 作者姓名： | 马军 马绍汉 |
| |
| 作者单位： | 山东大学计算机科学系，山东大学计算机科学系 |
| |
| 摘 要： | 本文给出了一个求解图中最大团的异步并行算法。在算法中采用了最优先搜索和分枝限界法等人工智能搜索技术,避免了无意义的搜索。其特点是易于在共享内存多处理机的并行计算机上实现,其执行时间曲线表明,对图中任意2点之间边存在概率小于1/3的无向图,具有较高效率的求解过程。还给出了在一定条件限制下,求解 NP—完全问题的方法。
|
| 关 键 词： | 无向图 团 二叉树 分枝限界法 并行算法 |
A PARALLEL ALGORITHM FOR FINDING A MAXIMUM CLIQUE |
| |
| Ma Jun Ma Shaohan.A PARALLEL ALGORITHM FOR FINDING A MAXIMUM CLIQUE[J].Journal of Shandong University,1990(3). |
| |
| Authors: | Ma Jun Ma Shaohan |
| |
| Abstract: | An improved parallel algorithm for finding a maxinum clique in a graph is given.The new algorithm is an asynchronous parallel algorithm and can be easily implemented in a MIMD-SM type computer system.The Best-First Search,Branch and Bound are used to delete unnecessary searches.The elaped execution time of the new parallel algorithm shows that the new algorithm will be efficient for the graphs in which the probability of edge existence between two vertices is less than 1/3.This study also gives a way to solve some NP-Complete problem within some limits. |
| |
| Keywords: | graph clique binary tree branch and bound method parallel algorithm |
| 本文献已被 CNKI 等数据库收录！ |
