摘要
本文给出了一个求解图中最大团的异步并行算法。在算法中采用了最优先搜索和分枝限界法等人工智能搜索技术,避免了无意义的搜索。其特点是易于在共享内存多处理机的并行计算机上实现,其执行时间曲线表明,对图中任意2点之间边存在概率小于1/3的无向图,具有较高效率的求解过程。还给出了在一定条件限制下,求解 NP—完全问题的方法。
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.
出处
《山东大学学报（自然科学版）》
CSCD
1990年第3期302-307,共6页
Journal of Shandong University(Natural Science Edition)
关键词
无向图
团
二叉树
并行算法
graph
clique
binary tree
branch and bound method
parallel algorithm
