On using the adjacency matrix power method for perception of symmetry and for isomorphism testing of highly intricate graphs.
Research output: Journal contributions › Journal articles › Research › peer-review
Standard
In: Journal of Chemical Information and Computer Science, Vol. 31, No. 1, 01.02.1991, p. 123-126.
Research output: Journal contributions › Journal articles › Research › peer-review
Harvard
APA
Vancouver
Bibtex
}
RIS
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 -