An Algorithm to Find the Upper Bound of the Distance Between Graphs

The problem of finding the distance between two graphs is known to be NP-complete. In this paper, we describe a heuristic algorithm that uses simulated annealing to find an upper bound for the distance between two graphs. One of the motivations for developing such an algorithm comes from our interest in finding the diameter of families of non-isomorphic extremal graphs. We tested our algorithm on each family of extremal graphs with up to \(16\) vertices and show that the exact distance was obtained in all cases.