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
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(73.2KB)
>>Buy this Article


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*(42nnlog 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*(42n), saving the nlog n factor.