The Kth Traveling Salesman Problem is Pseudopolynomial when TSP is polynomial

arXiv1704.02782MaRDI QIDQ6285331FDOQ6285331

Authors: Brahim Chaourar 

Publication date: 10 April 2017

Abstract: Given an undirected graph $G=(V,E)$ with a weight function $cin{R}^E$, and a positive integer $K$, the Kth Traveling Salesman Problem (KthTSP) is to find $K$ Hamilton cycles $H_1,H_2,,\mathrm{...},H_K$ such that, for any Hamilton cycle $Hotin{H}_1,H_2,,\mathrm{...},H_K$, we have $c(H)geqc(H_i),i=1,2,\mathrm{...},K$. This problem is NP-hard even for $K$ fixed. We prove that KthTSP is pseudopolynomial when TSP is polynomial.

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

This page was built for publication: The Kth Traveling Salesman Problem is Pseudopolynomial when TSP is polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6285331)