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 R. Morris, "Scatter storage techniques," Comm. ACM, v. 11, 1968, pp. 38-44.
- 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
Additional Information
- © Copyright 1974 American Mathematical Society
- Journal: Math. Comp. 28 (1974), 833-838
- MSC: Primary 68A05
- DOI: https://doi.org/10.1090/S0025-5718-1974-0371134-8
- MathSciNet review: 0371134