Generation is constructing a complete list of a class of some combinatorial objects
without isomorphs. When the objects are graphs, the problem of avoiding isomorphism
tends to be difficult. The method developed to avoid isomorphic copies is one of the
main criteria that determine the efficiency of a generation process.
Generation by Canonical Construction Path (McKay 1998) is a general method to
recursively generate combinatorial objects. In this method, larger objects, (children),
are constructed out of smaller ones, (parents), through some well-defined operation,
(extension), and avoiding constructing isomorphic copies at each construction step. The
inverse operation of the extension is called reduction. A unique genuine reduction is
defined for each graph but for the irreducible ones. An irreducible graph is one with no
parent. A generated graph is accepted only if it has been extended by some extension
where the inverse reduction of that extension is genuine.
This approach is time and storage efficient for discarding the isomorphic copies.
Based on this method, we have developed the most efficient software to generate Quartic graphs and some of its subclasses. We have also helped with the classification of
subfactors of von Neumann algebra, by providing an efficient generation of Principal
Date:||Wednesday, November 20, 2013 at 12:00-12:30
|Place: ||Niavaran Bldg., Niavaran Square, Tehran, Iran|