000070658 001__ 70658 000070658 005__ 20190709135421.0 000070658 0247_ $$2doi$$a10.1016/j.ejor.2016.07.060 000070658 0248_ $$2sideral$$a97032 000070658 037__ $$aART-2017-97032 000070658 041__ $$aeng 000070658 100__ $$0(orcid)0000-0002-6519-1472$$aGarcía, A.$$uUniversidad de Zaragoza 000070658 245__ $$aPolynomially solvable cases of the bipartite traveling salesman problem 000070658 260__ $$c2017 000070658 5060_ $$aAccess copy available to the general public$$fUnrestricted 000070658 5203_ $$aGiven 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. 000070658 536__ $$9info:eu-repo/grantAgreement/ES/DGA/E58$$9info:eu-repo/grantAgreement/ES/MINECO/MTM2012-30951$$9info:eu-repo/grantAgreement/ES/MINECO/MTM2015-63791-R 000070658 540__ $$9info:eu-repo/semantics/openAccess$$aby-nc-nd$$uhttp://creativecommons.org/licenses/by-nc-nd/3.0/es/ 000070658 590__ $$a3.428$$b2017 000070658 591__ $$aOPERATIONS RESEARCH & MANAGEMENT SCIENCE$$b12 / 83 = 0.145$$c2017$$dQ1$$eT1 000070658 592__ $$a2.437$$b2017 000070658 593__ $$aInformation Systems and Management$$c2017$$dQ1 000070658 593__ $$aModeling and Simulation$$c2017$$dQ1 000070658 593__ $$aManagement Science and Operations Research$$c2017$$dQ1 000070658 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/acceptedVersion 000070658 700__ $$0(orcid)0000-0002-9543-7170$$aTejel, J.$$uUniversidad de Zaragoza 000070658 7102_ $$12007$$2265$$aUniversidad de Zaragoza$$bDpto. Métodos Estadísticos$$cÁrea Estadís. Investig. Opera. 000070658 773__ $$g257, 2 (2017), 429-438$$pEur. J. oper. res.$$tEuropean Journal of Operational Research$$x0377-2217 000070658 8564_ $$s376659$$uhttps://zaguan.unizar.es/record/70658/files/texto_completo.pdf$$yPostprint 000070658 8564_ $$s82873$$uhttps://zaguan.unizar.es/record/70658/files/texto_completo.jpg?subformat=icon$$xicon$$yPostprint 000070658 909CO $$ooai:zaguan.unizar.es:70658$$particulos$$pdriver 000070658 951__ $$a2019-07-09-11:26:45 000070658 980__ $$aARTICLE