计算机工程 ›› 2010, Vol. 36 ›› Issue (06): 39-41.doi: 10.3969/j.issn.1000-3428.2010.06.013

• 软件技术与数据库 • 上一篇    下一篇

低度图的最大团求解算法

王青松,范铁生   

  1. (辽宁大学信息学院,沈阳 110036)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-03-20 发布日期:2010-03-20

Solution Algorithm for Maximum Clique in Low-degree Graphs

WANG Qing-song, FAN Tie-sheng   

  1. (Information Institute of Liaoning University, Shenyang 110036)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-03-20 Published:2010-03-20

摘要: 在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d)。给出一种求解低度图的最大团的确定性算法。该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题。算法时间复杂度为O(d•n3)。其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m。

关键词: 最大团问题, 图论, 图论算法, NP问题, 独立集

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.

Key words: Maximum Clique Problem(MCP), graph theory, graph theory algorithms, NP problem, independent set

中图分类号: