版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Russian Acad Sci Sobolev Inst Math Siberian Branch Novosibirsk 630090 Russia
出 版 物:《PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS》 (斯捷克洛夫数学研究所汇报)
年 卷 期:2011年第272卷第1-Sup期
页 面:1-13页
核心收录:
学科分类:07[理学] 0701[理学-数学] 070101[理学-基础数学]
基 金:Russian Foundation for Basic Research [08-01-00516, 10-07-00195] Presidium of the Russian Academy of Sciences [2, 227] Siberian Branch of the Russian Academy of Sciences
主 题:maximum traveling salesman problem edge-disjoint Hamiltonian circuits polynomial-time algorithm asymptotic optimality multidimensional Euclidean space
摘 要:An efficient algorithm A with a guaranteed error estimate is presented for solving the problem of finding several edge-disjoint Hamiltonian circuits (traveling salesman tours) of maximum weight in a complete weighted undirected graph in a multidimensional Euclidean space ae (k) . The time complexity of the algorithm is O(n (3)). The number of traveling salesman tours for which the algorithm is asymptotically optimal is established.