Article ID Journal Published Year Pages File Type
1143196 Operations Research Letters 2008 6 Pages PDF
Abstract
We show that searching the k-change neighborhood is W[1]-hard for metric TSP, which means that finding the best tour in the k-change neighborhood essentially requires complete search (modulo some complexity-theoretic assumptions).
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Searching the k-change neighborhood for TSP is W[1]-hard
Authors
,