Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication

DOI10.1145/3357713.3384264OpenAlexW3035322289MaRDI QIDQ5144895

Jesper Nederlof

Publication date: 19 January 2021

Published in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3357713.3384264

zbMATH Keywords

traveling salesman problemexponential time algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices, The Asymmetric Travelling Salesman Problem In Sparse Digraphs.