COMPUTATIONAL TECHNIQUES FOR THE AUTOMORPHISM-GROUPS OF GRAPHS

被引：16

作者：

BALASUBRAMANIAN, K

机构：

[1] Department of Chemistry and Biochemistry, Arizona State University, Tempe

来源：

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES | 1994年 / 34卷 / 03期

关键词：

D O I：

10.1021/ci00019a022

中图分类号：

O6 [化学];

学科分类号：

0703 ;

摘要：

The algorithm developed by Razinger et al. for the automorphism group of a graph is significantly improved by eliminating the CPU-intensive n3 matrix multiplication operations. The CPU times of the two algorithms are compared. The new algorithm based on memory manipulation reduces the required CPU time for some graphs by a factor of approximately 3350. For example, the new algorithm took 1 min, 29 s of CPU time for a graph containing 16 vertices, while the algorithm of Razinger et al. took 82 h, 54 min, 26 s for the same graph on an IBM RS6000/580 system.

引用

页码：621 / 626

页数：6

共 24 条

[1] UNIQUE DESCRIPTION OF CHEMICAL STRUCTURES BASED ON HIERARCHICALLY ORDERED EXTENDED CONNECTIVITIES (HOC PROCEDURES) .1. ALGORITHMS FOR FINDING GRAPH ORBITS AND CANONICAL NUMBERING OF ATOMS [J].