Polynomially solvable cases of the bipartite traveling salesman problem
详细信息 查看全文
- 作者：Alfredo Garcí ; a olaverri@unizar.es" class="auth_mail" title="E-mail the corresponding author ; Javier Tejel ; jtejel@unizar.es" class="auth_mail" title="E-mail the corresponding author
- 关键词：Traveling salesman ; Combinatorial optimization ; Bipartite traveling salesman ; quadrangle property ; Kalmanson matrix
- 刊名：European Journal of Operational Research
- 出版年：2017
- 出版时间：1 March 2017
- 年：2017
- 卷：257
- 期：2
- 页码：429-438
- 全文大小：756 K
文摘
- em" id="list_celist0003">
- •
We study the bipartite traveling salesman problem when the quadrangle property holds.
- •
For this problem, we show that an optimum tour is a twisted sequence.
- •
We provide an <em>Oem>(<em>nem>6) algorithm to find the shortest twisted sequence.
- •
We solve the problem for convex point sets, simple polygons and circular graphs.
- •
We describe an <em>Oem>(<em>nem>2) algorithm to solve the same problem for circular graphs.