IEICE TRANSACTIONS on Information
Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem
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.
- 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
Authors
Mohd SHAHRIZAN OTHMAN
Kyoto University
Aleksandar SHURBEVSKI
Kyoto University
Hiroshi NAGAMOCHI
Kyoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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*(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.
URL: https://global.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*(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.},
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*(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.
ER -
English
