图的最大二等分问题的一种离散填充函数算法

摘要：

图的最大二等分问题是一个经典的NP困难问题,有着广泛的应用背景.提出了一类求解最大二等分问题的离散填充函数算法.该算法采用快速的、基于迭代改进的算法作为局部搜索算法.构造了最大二等分问题的填充函数和辅助问题,并研究了该辅助问题的相关性质.利用局部搜索算法极大化辅助问题来寻找更好的解.用顶点数为800到10000的大规模标准测试例子测试提出的算法.实验结果表明,该算法是有效的.

关键词：最大二等分、填充函数、启发式、局部搜索

所属期刊栏目：52

分类号：O221.4(运筹学)

资助基金：国家自然科学基金11226236,11301255;福建省自然科学基金2012J05007;福建省中青年教师教育科研项目JA13246,JK2012037

在线出版日期：2016-06-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：27-32