2021/04/21 by Heping Jiang, Jiang, Heping
Biochemistry, Genetics and Molecular Biology · Computer Science · #05C85 68W01 #Algorithms and Data Compression #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #cs.DM #msc:05C85 #msc:68W01
paper · pdf · doi:10.48550/arxiv.2104.13197
10 pages, 7 figures
arxiv created 2021/04/21 · openalex publication_date 2021/04/21 · arxiv updated 2021/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Travelling Salesman Problem (TSP), finding a minimal weighted Hamilton cycle in a graph, is a typical problem in operation research and combinatorial optimization. In this paper, based on some novel properties on Hamilton graphs, we present a precise algorithm for finding a minimal weighted Hamilton cycle in a non-metric and symmetric graph with time complexity of O(|E(G)|3) , where |E(G)| is the size of graph G.