[1]张亚玲,龙熙华,穆学文.求解最大割问题的分枝定界算法[J].西安科技大学学报,2006,(04):541-544.[doi:10.3969/j.issn.1672-9315.2006.04.025]
 ZHANG Ya-ling LONG Xi-hua MU Xue-wen.The branch-and-bound algorithm for max-cut problem[J].Journal of Xi'an University of Science and Technology,2006,(04):541-544.[doi:10.3969/j.issn.1672-9315.2006.04.025]
点击复制

求解最大割问题的分枝定界算法()
分享到:

西安科技大学学报[ISSN:1672-9315/CN:61-1434/N]

卷:
期数:
2006年04期
页码:
541-544
栏目:
出版日期:
2006-12-29

文章信息/Info

Title:
The branch-and-bound algorithm for max-cut problem
作者:
张亚玲龙熙华穆学文
西安科技大学,计算机系,陕西,西安,710054,西安电子科技大学,应用数学系,陕西,西安,710071
Author(s):
ZHANG Ya-ling LONG Xi-hua MU Xue-wen
关键词:
最大割问题 二次规划 分枝定界
分类号:
O221.7
DOI:
10.3969/j.issn.1672-9315.2006.04.025
摘要:
最大割问题是图论中的一个典型的NP困难问题.文中基于最大割问题的半定规划松弛模型,给出了最大割问题的一种二次规划松弛模型,并且理论证明了提出的二次规划松弛模型要优于半定规划松弛模型.在该模型的基础上,利用分枝定界算法求解最大割问题.对小规模和中等规模的最大割问题分别作数值实验.实验表明分枝定界算法能够给出最大割问题一个好的近似解,是求解中小规模最大割问题的有效方法.
更新日期/Last Update: 2006-12-29