TY - JOUR

T1 - On using the adjacency matrix power method for perception of symmetry and for isomorphism testing of highly intricate graphs.

AU - Rücker, Christoph

AU - Rücker, Gerta

PY - 1991/2/1

Y1 - 1991/2/1

N2 - A modification of the adjacency matrix power method described recently for the perception of symmetry in graphs is introduced, which expands the limits of the method far beyond the realm of chemically interesting graphs. The procedure finds the automorphism partition even for intricate graphs without performing a tree search. The calculation effort increases with the problem size polynomially for all tested cases, including strongly regular graphs, two-level regular graphs, and graphs corresponding to balanced incomplete block designs (BIBD). An equally powerful computer program for testing isomorphism of graphs based on the adjacency matrix power method is introduced.

AB - A modification of the adjacency matrix power method described recently for the perception of symmetry in graphs is introduced, which expands the limits of the method far beyond the realm of chemically interesting graphs. The procedure finds the automorphism partition even for intricate graphs without performing a tree search. The calculation effort increases with the problem size polynomially for all tested cases, including strongly regular graphs, two-level regular graphs, and graphs corresponding to balanced incomplete block designs (BIBD). An equally powerful computer program for testing isomorphism of graphs based on the adjacency matrix power method is introduced.

KW - Chemistry

UR - http://www.scopus.com/inward/record.url?scp=0026112345&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/545c7a09-d621-3364-84a7-03c1323a90f3/

U2 - 10.1021/ci00001a022

DO - 10.1021/ci00001a022

M3 - Journal articles

VL - 31

SP - 123

EP - 126

JO - Journal of Chemical Information and Computer Science

JF - Journal of Chemical Information and Computer Science

SN - 1520-5142

IS - 1

ER -