Fast Backtracking Principles Applied to Find New Cages
Brendan D. McKay, Wendy J. Myrvold, Jacqueline Nadon · 1997
We describe how standard backtracking rules of thumb were successfully applied to the problem of characterizing (3;g)-cages, the minimum order 3-regular graphs of girth g. It took just 5 days of cpu time (compared to 259 days for previous authors) to verify the (3; 9)-cages, and we were able to con rm that (3; 11)-cages have order 112 for the rst time ever. The lower bound for a (3; 13)-cage is improved from 196 to 202 using the same approach. Also, we determined that a (3; 14)-cage has order at least 258.