IEICE Trans - Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem

Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem

Mohd SHAHRIZAN OTHMAN  Aleksandar SHURBEVSKI  Hiroshi NAGAMOCHI

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.3   pp.611-612
Publication Date: 2018/03/01
Publicized: 2017/12/19
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017FCL0003
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science — Frontiers of Theoretical Computer Science —)
Category:
Keyword:
bipartite traveling salesman problem,  exact algorithms,  polynomial space,  divide-and-conquer,  Stirling's formula,

Full Text: PDF>>

Summary:
Given an edge-weighted bipartite digraph G=(A,B;E), the Bipartite Traveling Salesman Problem (BTSP) asks to find the minimum cost of a Hamiltonian cycle of G, or determine that none exists. When |A|=|B|=n, the BTSP can be solved using polynomial space in O^*(4²ⁿn^{log n}) time by using the divide-and-conquer algorithm of Gurevich and Shelah (SIAM Journal of Computation, 16(3), pp.486-502, 1987). We adapt their algorithm for the bipartite case, and show an improved time bound of O^*(4²ⁿ), saving the n^{log n} factor.