Cyclotomic Birman–Wenzl–Murakami Algebras, II Admissibility Relations and Freeness.pdfVIP

An Improved Exact Algorithm for TSP in Degree-4 Graphs Mingyu Xiao1 and Hiroshi Nagamochi2 1 School of Computer Science and Engineering, University of Electronic Science and Technology of China, China myxiao@ 2 Graduate School of Informatics, Kyoto University, Japan nag@amp.i.kyoto-u.ac.jp Abstract. The paper presents an O∗ (1.716n )-time polynomial-space al- gorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the O∗ (1.890n )-time polynomial-space algorithm by Eppstein and the O∗ (1.733n )-time exponential-space algorithm by Gebauer. Keywords: Traveling Salesman Problem, Exact Exponential Algorithm, Graph Algorithm. 1 Introduction The famous traveling salesman problem (TSP) was first formulated as a mathe- matical problem in 1930s and is one of the most intensively studied problems in optimization. A large number of heuristics and exact methods for it are known. A classical dynamic programming solution with running time O∗ (2n ) for it was discovered in early 1960s, where n is the number of vertices in the graph. Despite the great progress in the pass half a century on exact exponential algorithms and their worst-case analysis for other basic NP-hard optimization problems, such as the maximum independent set problem, the CNF satisfiability problem and so on, it seems very hard to break the barrier of 2 in the basic of the expo- nential part for TSP [8]. To make steps toward the long-standing open problem of designing an O∗ (1.99n ) algorithm for TSP, researchers have interests in find- ing fast solutions to the problem in special classes of graphs,