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

• 作者: 彭济根 郑开杰 高玉涛
• 来源期刊: 自动化学报
• 关键词: 图匹配 松弛方法 置换矩阵 NP难问题
• 年，卷（期）: 2010,（8）
• 页码范围: 1200-1203
• 页数: 4页
• 语种: 中文
• DOI: 10.3724/SP.J.1004.2010.01200

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	彭济根		29	173	7.0	12.0
2	郑开杰		4	10	2.0	3.0
3	高玉涛		2	0	0.0	0.0