For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem
Mohd SHAHRIZAN OTHMAN Aleksandar SHURBEVSKI Hiroshi NAGAMOCHI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2018/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science — Frontiers of Theoretical Computer Science —)
bipartite traveling salesman problem, exact algorithms, polynomial space, divide-and-conquer, Stirling's formula,
Full Text: PDF>>
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.