基于Q0-1规划模型用分枝定界法求解最大团问题

• 作者: 续晓欣 贾晓峰
• 来源期刊: 太原理工大学学报
• 关键词: 最大团 Q0-1规划 分枝定界法 梯度
• 年，卷（期）: 2008,（6）
• 所属期刊栏目: 基础理论
• 页码范围: 636-639
• 页数: 4页
• 分类号: O157
• 语种: 中文

摘要

搜索图的最大团是经典的NP-难题.通过运用二次0-1规划模型(简称Q0-1规划模型)寻得最大团问题的解法,所用的分枝定界法建立在此模型之上.通过一个命题推导出图的最大团求解问题与一类特殊Q0-1规划的等价性,借助于求解一般Q0-1规划的分枝定界法推演出求最大团问题的分枝定界规则,从而将图论中的经典问题转化成代数问题加以解决,并给出实例说明该算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	续晓欣	中北大学应用数学系	19	12	2.0	2.0
2	贾晓峰	太原理工大学理学院	16	44	4.0	5.0