ICS Theory Group

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.