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

Corrigendum to the approximation analysis of a Max_TSP algorithm

作　　者：翟同悦 张安[1] 舒巧君[1] 陈永[1] 陈光亭[2] ZHAI Tongyue;ZHANG An;SHU Qiaojun;CHEN Yong;CHEN Guangting(School of Sciences,Hangzhou Dianzi University,Hangzhou Zhejiang 310018,China;School of Electronics and Information Engineering,Taizhou University,Taizhou Zhejiang 318000,China)

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018 [2]台州学院电子与信息工程学院,浙江台州318000

出　　处：《杭州电子科技大学学报（自然科学版）》2023年第1期88-92,共5页Journal of Hangzhou Dianzi University：Natural Sciences

基　　金：国家自然科学基金资助项目(11771114,11971139);浙江省自然科学基金资助项目(LY21A010014)。

摘　　要：基于极大化P_(3)-填充,研究并设计Max_TSP算法。研究发现,Hassin等之前发表在《Information Processing Letters》上的一文中,任意边染色方案可能出现顶点相交的3-边路径的情况,即辅助图的边染色方案无效。在此基础上,通过反例说明其错误所在,并给出有效的边染色方案,更正了该算法的近似分析。This paper revisits a Max_TSP algorithm designed through a maximum P_(3)-packing,which is previously published in Information Processing Letters.We first point out an error in the analysis of the algorithm that the coloring of edges on the auxiliary graph is invalid.Then we construct a new auxiliary graph and provide a valid coloring scheme for it.This corrects the approximation analysis of the known algorithm.

关 键 词：最大旅行商问题 极大化P 3-填充 边染色 匹配 近似分析 

分 类 号：O221.7[理学—运筹学与控制论]