求解图的最大团的一种算法

被引：15

作者：

仲盛

谢立

机构：

[1] 南京大学计算机科学与技术系

来源：

基金：

国家攀登计划;

关键词：

图论; 图论算法; 可计算性; NP问题; 集团;

D O I：

10.13328/j.cnki.jos.1999.03.012

中图分类号：

O157 [组合数学（组合学）];

学科分类号：

070104 ;

摘要：

图的最大团问题是一个著名的ＮＰ－完全问题．现有求解图的最大团的算法或者只适用于某些特殊的图，或者需要指数级时间代价，效率较低．以图的区间表示的概念为基础，提出了一种求解最大团的算法．该算法能够适用于任意的简单图，并且在一定的条件下，该算法只需要多项式时间就可以完成运行

引用

页码：65 / 69

页数：5