The bipartite travelling salesman problem: A pyramidally solvable case

Vladimir G. Deineko, Bettina Klinz, Gerhard J. Woeginger

In the bipartite travelling salesman problem (BTSP), we are given $n=2k$ cities along with an $n\times n$ distance matrix and a partition of the cities into $k$ red and $k$ blue ci…