ICS 269, Spring 1997: Theory Seminar
2 May 1997:
Non-Isomorphic Graph Generation
Brad Hutchings, ICS, UC Irvine
Time and space efficient non-isomorphic graph generation may have
applications in graph compression, generating graph catalogs, and
computationally looking at properties of sets of graphs. Brendan McKay's paper
Isomorph-Free Exhaustive Generation presents an abstract
framework that can be applied to many interesting graph and
non-graph generation problems. I will discuss two graph generation
problems, Maximal Planar Graphs and Triangle Free Graphs. I will
then explain how McKay's general method applies to graph problems
and compare with selected graph generation schemes.