Graph automorphism perception algorithms in computer-enhanced structure elucidation

J Chem Inf Comput Sci. 1993 Mar-Apr;33(2):197-201. doi: 10.1021/ci00012a003.

Abstract

The concept of graph symmetry is explained in terms of the vertex automorphism group, which is a subgroup of the complete vertex permutation group. The automorphism group can be deduced from the automorphism partition of graph vertices. An algorithm is described which constructs the automorphism group of a graph from the automorphism vertex partitioning. The algorithm is useful especially for graphs which contain more than one vertex-partition set. Several well-known topological symmetry perception algorithms that yield automorphism partitions are compared. The comparison is favorable to the Shelley-Munk algorithm, developed in the framework of the SESAMI system for computer-enhanced structure elucidation.

Publication types

  • Research Support, Non-U.S. Gov't
  • Research Support, U.S. Gov't, P.H.S.

MeSH terms

  • Algorithms*
  • Computer Graphics
  • Molecular Structure*
  • Software