HSAGA and its application for the construction of near-Moore digraphs (Q954960): Difference between revisions

The degree/diameter problem is to determine the largest (di-)graphs of given maximum (out-)degree \(d\) and given diameter \(k\), see the survey by \textit{M. Miller} and \textit{J. Širáň} [Electron. J. Comb. DS14, Dynamic Surveys, 61 p., electronic only (2005; Zbl 1079.05043)]. An upper bound for the number of vertices of such graphs is known as Moore bound. There are no digraphs meeting this bound for \(d \geq 2\) and \(k \geq 2\). The authors describe randomised algorithms to find directed near-Moore graphs. More precisely, HSAGA means hybrid simulated annealing and genetic algorithm.