一个Max_TSP算法的近似分析勘误

• 作者: 翟同悦 张安 舒巧君 陈永 陈光亭
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 最大旅行商问题 极大化P3-填充 边染色 匹配 近似分析
• 年，卷（期）: 2023,（1）
• 页码范围: 88-92
• 页数: 4页
• 分类号: O221.7
• 语种: 中文
• DOI: 10.13954/j.cnki.hdu.2023.01.014

摘要

基于极大化P3-填充，研究并设计Max_TSP算法。研究发现，Hassin等之前发表在《Information Processing Letters》上的一文中，任意边染色方案可能出现顶点相交的3-边路径的情况，即辅助图的边染色方案无效。在此基础上，通过反例说明其错误所在，并给出有效的边染色方案，更正了该算法的近似分析。