Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4960056 | European Journal of Operational Research | 2017 | 10 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Alfredo GarcÃa, Javier Tejel,