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 条

[11] COMPUTER-ASSISTED GRAPH-THEORETICAL CONSTRUCTION OF C-13 NMR SIGNAL AND INTENSITY PATTERNS [J].

LIU, XY ;

BALASUBRAMANIAN, K ;

MUNK, ME .

JOURNAL OF MAGNETIC RESONANCE, 1990, 87 (03) :457-474

[12] GENERATION OF A UNIQUE MACHINE DESCRIPTION FOR CHEMICAL STRUCTURES-A TECHNIQUE DEVELOPED AT CHEMICAL ABSTRACTS SERVICE [J].

MORGAN, HL .

JOURNAL OF CHEMICAL DOCUMENTATION, 1965, 5 (02) :107-&

[13]

NIJENHUIS A, 1975, COMBINATORIAL ALGORI

[14] DISCERNING SYMMETRY PROPERTIES OF GRAPHS [J].

RANDIC, M .

CHEMICAL PHYSICS LETTERS, 1976, 42 (02) :283-287

[15] SYMMETRY PROPERTIES OF CHEMICAL GRAPHS .6. ISOMERIZATIONS OF OCTAHEDRAL COMPLEXES [J].

RANDIC, M ;

DAVIS, MI .

INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, 1984, 26 (01) :69-89

[16] SYMMETRY PROPERTIES OF GRAPHS OF INTEREST IN CHEMISTRY .2. DESARGUES-LEVI GRAPH [J].

RANDIC, M .

INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, 1979, 15 (06) :663-682

[17] RECOGNITION OF IDENTICAL GRAPHS REPRESENTING MOLECULAR TOPOLOGY [J].

RANDIC, M .

JOURNAL OF CHEMICAL PHYSICS, 1974, 60 (10) :3920-3928

[18] GRAPH AUTOMORPHISM PERCEPTION ALGORITHMS IN COMPUTER-ENHANCED STRUCTURE ELUCIDATION [J].

RAZINGER, M ;

BALASUBRAMANIAN, K ;

MUNK, ME .

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1993, 33 (02) :197-201

[19]

RAZINGER M, 1982, THEOR CHIM ACTA, V61, P581, DOI 10.1007/BF02394734

[20] SIGNAL NUMBER PREDICTION IN C-13 NUCLEAR MAGNETIC-RESONANCE SPECTROMETRY [J].

SHELLEY, CA ;

MUNK, ME .

ANALYTICAL CHEMISTRY, 1978, 50 (11) :1522-1527