|
Computing all Graphs on 11 vertices in MapleMichael Monagan, CECM
Abstract: I will describe an algorithm of Reid and Colburn from 1981 to generate all graphs on n vertices and show some results for n=11 vertices using a Maple implementation of the algorithm. The main difficulty is space. There are 15, 24, 37, 53, 70, 86, 99, 106, and 108 million different graphs for 20, 21, 22, 23, 24, 25, 25, 27 and 28 edges, respectively. I will sketch out the details of how to do this in Maple. We can represent the graphs as 55 bit integers so that each graph, when encoded as an integer, can be stored in one word on a 64 bit computer in Maple. We compute 60 bit integer hash codes for each one from their characteristic polynomials to partition the large set of candidate graphs into small sets. Using a hash table in Maple to store the graphs, indexed by these hash codes, this requires asymptotically 2 words of storage per graph, hence, about 1.6 giga bytes of storage for storing 100 million graphs. |