Generating the nine-point graphs

Baker, H. H.; Dewdney, A. K.; Szilard, A. L.

doi:10.1090/S0025-5718-1974-0371134-8

Generating the nine-point graphs
HTML articles powered by AMS MathViewer

by H. H. Baker, A. K. Dewdney and A. L. Szilard PDF

Math. Comp. 28 (1974), 833-838 Request permission

Abstract:

A program has been written which recently generated all the (unlabelled) nine-point graphs. Written in MACRO-10 assembly language and run on a 165K PDP-10, it generates the complete set of 274,668 graphs in less than six hours. The algorithm on which this program is based is discussed with an emphasis on coding of graphs and various programming techniques designed to save space and time during execution. The methods developed may have applications in other combinatorial generating problems.

References

John E. Blackburn, Henry H. Crapo, and Denis A. Higgs, A catalogue of combinatorial geometries, Math. Comp. 27 (1973). MR 419270, DOI 10.1090/S0025-5718-1973-0419270-0
D. G. Corneil and C. C. Gotlieb, An efficient algorithm for graph isomorphism, J. Assoc. Comput. Mach. 17 (1970), 51–64. MR 278977, DOI 10.1145/321556.321562
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911
Selmer M. Johnson, Generation of permutations by adjacent transposition, Math. Comp. 17 (1963), 282–285. MR 159764, DOI 10.1090/S0025-5718-1963-0159764-2

Comm. ACM

Ronald C. Read (ed.), Graph theory and computing, Academic Press, New York-London, 1972. MR 0329941
Mark B. Wells, Elements of combinatorial computing, Pergamon Press, Oxford-New York-Toronto, Ont., 1971. MR 0277082