@article{Gutin_Karapetyan_2009, title={Generalized Traveling Salesman Problem Reduction Algorithms}, volume={4}, url={https://journals.lib.unb.ca/index.php/AOR/article/view/5660}, abstractNote={The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The aim of this paper is to present a problem reduction algorithm that deletes redundant vertices and edges, preserving the optimal solution. The algorithm’s running time is O(N<sup>3</sup>) in the worst case, but it is significantly faster in practice. The algorithm has reduced the problem size by 15–20% on average in our experiments and this has decreased the solution time by 10–60% for each of the considered solvers.}, number={2}, journal={Algorithmic Operations Research}, author={Gutin, Gregory and Karapetyan, Daniel}, year={2009}, month={Sep.}, pages={Pages 144 – 154} }