首页 | 官方网站   微博 | 高级检索  
     

低度图的最大团求解算法
引用本文:王青松,范铁生. 低度图的最大团求解算法[J]. 计算机工程, 2010, 36(6): 39-41
作者姓名:王青松  范铁生
作者单位:辽宁大学信息学院,沈阳,110036
基金项目:辽宁大学“211”三期工程基金资助项目
摘    要:在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d)。给出一种求解低度图的最大团的确定性算法。该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题。算法时间复杂度为O(d•n3)。其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m。

关 键 词:最大团问题  图论  图论算法  NP问题  独立集
修稿时间: 

Solution Algorithm for Maximum Clique in Low-degree Graphs
WANG Qing-song,FAN Tie-sheng. Solution Algorithm for Maximum Clique in Low-degree Graphs[J]. Computer Engineering, 2010, 36(6): 39-41
Authors:WANG Qing-song  FAN Tie-sheng
Affiliation:(Information Institute of Liaoning University, Shenyang 110036)
Abstract:In the Maximum Clique Problem(MCP), setting m as a threshold means that it is easy to compute MCP of a graph whose vertices are not greater than m, and the time complexity is O(d). An exact algorithm to compute MCP in low-degree graphs is presented. The algorithm solves MCP successfully by dividing the vertices of the graph gradually and computing MCP separately. The algorithm is easy to be realized, and the time complexity is O(d•n3). n represents graph vertices, the maximum degree of vertex in graph is lower than m, or the graph can make all the vertex degree lower than m by gradually deleting the vertices which are lower than m.
Keywords:Maximum Clique Problem(MCP)  graph theory  graph theory algorithms  NP problem  independent set
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机工程》浏览原始摘要信息
点击此处可从《计算机工程》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号