The bipartite travelling salesman problem: A pyramidally solvable case

Vladimir Deineko, Bettina Klinz*, Gerhard J. Woeginger

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number107130
JournalOperations Research Letters
Volume55
Early online date2024
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'The bipartite travelling salesman problem: A pyramidally solvable case'. Together they form a unique fingerprint.

Cite this