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