赋权图匹配问题的一种新的松弛模型

摘要：

图匹配是一个NP难(NP-hard)问题.基于置换矩阵是非负正交矩阵这一经典结论,提出赋权图匹配(Weighted graph matching,WGM)的双向松弛障碍规划,理论上证明新模型的解与原模型的解是一致的.该规划是一个二元连续规划,它是正交矩阵上的线性优化问题,同时也是非负矩阵上的凸二次优化问题.故设计求解新模型的交替迭代算法,并证明算法的局部收敛性.数值实验表明,在匹配精度方面,新方法强于线性规划方法和特征值分解方法.

关键词：图匹配、松弛方法、置换矩阵、NP难问题

所属期刊栏目：36

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金60970149;福建省教育厅B类基金JB07050

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

页码：1200-1203