70658 20190709135421.0 doi 10.1016/j.ejor.2016.07.060 sideral 97032 ART-2017-97032 eng (orcid)0000-0002-6519-1472 García, A. Universidad de Zaragoza Polynomially solvable cases of the bipartite traveling salesman problem 2017 Access copy available to the general public Unrestricted Given two sets, R and B, consisting of n cities each, in the bipartite traveling salesman problem one looks for the shortest way of visiting alternately the cities of R and B, returning to the city of origin. This problem is known to be NP-hard for arbitrary sets R and B. In this paper we provide an O(n6) algorithm to solve the bipartite traveling salesman problem if the quadrangle property holds. In particular, this algorithm can be applied to solve in O(n6) time the bipartite traveling salesman problem in the following cases: S=R¿B is a convex point set in the plane, S=R¿B is the set of vertices of a simple polygon and V=R¿B is the set of vertices of a circular graph. For this last case, we also describe another algorithm which runs in O(n2) time. info:eu-repo/grantAgreement/ES/DGA/E58 info:eu-repo/grantAgreement/ES/MINECO/MTM2012-30951 info:eu-repo/grantAgreement/ES/MINECO/MTM2015-63791-R info:eu-repo/semantics/openAccess by-nc-nd http://creativecommons.org/licenses/by-nc-nd/3.0/es/ 3.428 2017 OPERATIONS RESEARCH & MANAGEMENT SCIENCE 12 / 83 = 0.145 2017 Q1 T1 2.437 2017 Information Systems and Management 2017 Q1 Modeling and Simulation 2017 Q1 Management Science and Operations Research 2017 Q1 info:eu-repo/semantics/article info:eu-repo/semantics/acceptedVersion (orcid)0000-0002-9543-7170 Tejel, J. Universidad de Zaragoza 2007 265 Universidad de Zaragoza Dpto. Métodos Estadísticos Área Estadís. Investig. Opera. 257, 2 (2017), 429-438 Eur. J. oper. res. European Journal of Operational Research 0377-2217 376659 http://zaguan.unizar.es/record/70658/files/texto_completo.pdf Postprint 82873 http://zaguan.unizar.es/record/70658/files/texto_completo.jpg?subformat=icon icon Postprint oai:zaguan.unizar.es:70658 articulos driver 2019-07-09-11:26:45 ARTICLE