November 22, 2000 from 3:30 - 4:30 in K9509, SFU
"Algorithms for Generation of Discrete Structures"
Abstract: We will survey algorithms for isomorph-free (i.e. redundancy-free) generation of various discrete structures, such as graphs, linear codes or certain geometric configurations. The mathematical foundations of these algorithms can be roughly divided into three streams (orderly generation, generation by canonical path, homomorphism methods). Group-theoretical methods as well as algorithms for efficient computation with permutation groups play an important role in all of them. We will also include examples of restricted generation, such as generating structures with a prescribed automorphism group. Applications in discrete mathematics and in sciences will be presented.