Weakly Symmetric Graphs, Elementary Landscapes, and the TSP

Abstract

Weakly symmetric graphs are defined and their construction from symmetric graphs is explained. It is shown that the TSP on a weakly symmetric graph joined with each of a number of well-known local search neighbourhoods yields elementary landscapes (in which local minima are better than the average). In conclusion, an O(n²) algorithm for identifying weakly symmetric graphs is described.