低度图的最大团求解算法

摘要：

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

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

所属期刊栏目：36

分类号：TP301.6(计算技术、计算机技术)

资助基金：辽宁大学"211"三期工程基金

在线出版日期：2010-05-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：39-41