Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem

Mohd SHAHRIZAN OTHMAN; Aleksandar SHURBEVSKI; Hiroshi NAGAMOCHI

doi:10.1587/transinf.2017FCL0003

Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem

Mohd SHAHRIZAN OTHMAN, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Information 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

Cite this

Copy

Mohd SHAHRIZAN OTHMAN, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, "Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem" in IEICE TRANSACTIONS on Information, vol. E101-D, no. 3, pp. 611-612, March 2018, doi: 10.1587/transinf.2017FCL0003.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2017FCL0003/_p

Copy

@ARTICLE{e101-d_3_611,
author={Mohd SHAHRIZAN OTHMAN, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem},
year={2018},
volume={E101-D},
number={3},
pages={611-612},
abstract={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.},
keywords={},
doi={10.1587/transinf.2017FCL0003},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem
T2 - IEICE TRANSACTIONS on Information
SP - 611
EP - 612
AU - Mohd SHAHRIZAN OTHMAN
AU - Aleksandar SHURBEVSKI
AU - Hiroshi NAGAMOCHI
PY - 2018
DO - 10.1587/transinf.2017FCL0003
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2018
AB - 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.
ER -