10.3969/j.issn.1000-3428.2010.06.013
低度图的最大团求解算法
在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d).给出一种求解低度图的最大团的确定性算法.该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题.算法时间复杂度为O(d·n~3).其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m.
最大团问题、图论、图论算法、NP问题、独立集
36
TP301.6(计算技术、计算机技术)
辽宁大学"211"三期工程基金
2010-05-24(万方平台首次上网日期,不代表论文的发表时间)
共3页
39-41