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