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

作     者：翟同悦 张安 舒巧君 陈永 陈光亭 ZHAI Tongyue;ZHANG An;SHU Qiaojun;CHEN Yong;CHEN Guangting

作者机构：杭州电子科技大学理学院浙江杭州310018 台州学院电子与信息工程学院浙江台州318000 

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

出 版 物：《杭州电子科技大学学报（自然科学版）》 (Journal of Hangzhou Dianzi University：Natural Sciences)

年 卷 期：2023年第43卷第1期

页      码：88-92页

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

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

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

D　O　I：10.13954/j.cnki.hdu.2023.01.014

馆 藏 号：203118256...