Some relations between neighbourhood graphs for a permutation problem

What is it about?

Many discrete optimization problems belong to the class NP-hard. Therefore heuristics have been developed for such problems. The determination of a suitable neighbourhood plays an important role in iterive algorithms. In this paper we derive structural relationships between different neighbourhood graphs where the set of solutions is characterized by the set of permutations of the integers 1,…,m. For two neighbours in some graph, we calculate the mean shortest length in some other graph. We also derive the maximum difference of shortest lengths in both graphsbetween vertices which are connected in one graph.

Featured Image