Groupe d’études et de recherche en analyse des décisions

AutoGraphiX III - Description of the New Generation of AGX

Gilles Caporossi Professeur titulaire, Département de sciences de la décision, HEC Montréal, Canada

A graph invariant is a value that may be computed from a graph regardless the way vertices are labelled. Based upon the Variable Neighborhood Search (VNS) metaheuristic, the AutoGraphiX system (AGX) was developped in 1997 by Caporossi and Hansen. The principle of AGX is to search for extremal graphs (graphs maximizing or minimizing the value of an invariant or a function of invariants). This principle allows the study of various problems such as finding extremal graphs, refuting conjectures, finding conjectures, etc. Fifteen years later, the third generation of the software is now being developped providing a lot of significant improvements and some new features in order to better help the graph theorist in his work.

The new features and improvements of the system as well as a description of its usage will be described and illustrated by examples.