Polynomially solvable cases of the bipartite traveling salesman problem
García, A. (Universidad de Zaragoza) ; Tejel, J. (Universidad de Zaragoza)
Resumen: 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.
Idioma: Inglés
DOI: 10.1016/j.ejor.2016.07.060
Año: 2017
Publicado en: European Journal of Operational Research 257, 2 (2017), 429-438
ISSN: 0377-2217
Factor impacto JCR: 3.428 (2017)
Categ. JCR: OPERATIONS RESEARCH & MANAGEMENT SCIENCE rank: 12 / 83 = 0.145 (2017) - Q1 - T1
Factor impacto SCIMAGO: 2.437 - Information Systems and Management (Q1) - Modeling and Simulation (Q1) - Management Science and Operations Research (Q1)
Financiación: info:eu-repo/grantAgreement/ES/DGA/E58
Financiación: info:eu-repo/grantAgreement/ES/MINECO/MTM2012-30951
Financiación: info:eu-repo/grantAgreement/ES/MINECO/MTM2015-63791-R
Tipo y forma: Article (PostPrint)
Área (Departamento): Área Estadís. Investig. Opera. (Dpto. Métodos Estadísticos)
You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. You may not use the material for commercial purposes. If you remix, transform, or build upon the material, you may not distribute the modified material.
Exportado de SIDERAL (2019-07-09-11:26:45)
Visitas y descargas
Idioma: Inglés
DOI: 10.1016/j.ejor.2016.07.060
Año: 2017
Publicado en: European Journal of Operational Research 257, 2 (2017), 429-438
ISSN: 0377-2217
Factor impacto JCR: 3.428 (2017)
Categ. JCR: OPERATIONS RESEARCH & MANAGEMENT SCIENCE rank: 12 / 83 = 0.145 (2017) - Q1 - T1
Factor impacto SCIMAGO: 2.437 - Information Systems and Management (Q1) - Modeling and Simulation (Q1) - Management Science and Operations Research (Q1)
Financiación: info:eu-repo/grantAgreement/ES/DGA/E58
Financiación: info:eu-repo/grantAgreement/ES/MINECO/MTM2012-30951
Financiación: info:eu-repo/grantAgreement/ES/MINECO/MTM2015-63791-R
Tipo y forma: Article (PostPrint)
Área (Departamento): Área Estadís. Investig. Opera. (Dpto. Métodos Estadísticos)
You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. You may not use the material for commercial purposes. If you remix, transform, or build upon the material, you may not distribute the modified material. Exportado de SIDERAL (2019-07-09-11:26:45)
Permalink:
Visitas y descargas
Este artículo se encuentra en las siguientes colecciones:
Articles
Record created 2018-05-22, last modified 2019-07-09