Abstract
Given k blue cities, k red cities and a 2k x 2k distance matrix, the task in the bipartite travelling salesman problem is to find a shortest tour which alternately visits blue and red cities. We consider the special case of Van der Veen distance matrices and show that it remains NP-hard in general but can be solved in time O(k^2) when all vertices with odd indices are blue and all with even indices are red.
Original language | English |
---|---|
Article number | 107130 |
Journal | Operations Research Letters |
Volume | 55 |
Early online date | 2024 |
DOIs | |
Publication status | Published - Jul 2024 |
Keywords
- 63605ec6eb4e243dcb2eeb7d Van der Veen matrix
- Bipartite travelling salesman problem
- Combinatorial optimisation
- Pyramidally solvable case
- Recognition algorithm
ASJC Scopus subject areas
- Software
- Applied Mathematics
- Industrial and Manufacturing Engineering
- Management Science and Operations Research
Fields of Expertise
- Information, Communication & Computing