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

摘要

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