摘要
基于极大化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.
作者
翟同悦
张安
舒巧君
陈永
陈光亭
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)
出处
《杭州电子科技大学学报（自然科学版）》
2023年第1期88-92,共5页
Journal of Hangzhou Dianzi University：Natural Sciences
基金
国家自然科学基金资助项目(11771114,11971139)
浙江省自然科学基金资助项目(LY21A010014)。
