Polynomially solvable cases of the bipartite traveling salesman problem

Alfredo García and Javier Tejel

European Journal of Operational Research, 2017, vol. 257, issue 2, 429-438

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.

Keywords: Traveling salesman; Combinatorial optimization; Bipartite traveling salesman; quadrangle property; Kalmanson matrix (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716306166
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:257:y:2017:i:2:p:429-438

DOI: 10.1016/j.ejor.2016.07.060

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().