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

• 作 者: 林耿 徐梅琴
• 机 构: 闽江学院数学系,闽江学院人事处
• 出 处: 计算机工程与应用
• 发表日期: 2016年5期
• 关键词: 最大二等分 填充函数 启发式 局部搜索
• 基金项目: 国家自然科学基金(No.11226236,No.11301255);福建省自然科学基金(No.2012J05007);福建省中青年教师教育科研项目(No.JA13246,No.JK2012037)

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