Ring perception using breadth-first search

被引：41

作者：

Figueras, J

机构：

[1] Orleans, MA 02653

来源：

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES | 1996年 / 36卷 / 05期

关键词：

D O I：

10.1021/ci960013p

中图分类号：

O6 [化学];

学科分类号：

0703 ;

摘要：

Combining breadth-first search with new ideas for uncovering embedded rings in complex systems' yields a very fast routine for ring perception. With large structures, the new routine is orders of magnitude faster than depth-first ring detection, a result expected on the basis of recent work that establishes polynomial order for BFS.(2)

引用

页码：986 / 991

页数：6

共 9 条

[1] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2] EFFICIENT EXACT SOLUTION OF THE RING PERCEPTION PROBLEM
BALDUCCI, R
PEARLMAN, RS
[J]. JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1994, 34 (04): : 822 - 831
[3] DOUCET J, COMMUNICATION
[4] REVIEW OF RING PERCEPTION ALGORITHMS FOR CHEMICAL GRAPHS
DOWNS, GM
GILLET, VJ
HOLLIDAY, JD
LYNCH, MF
[J]. JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1989, 29 (03): : 172 - 187
[5] DERIVATION OF THE PRINCIPLE OF SMALLEST SET OF SMALLEST RINGS FROM EULER POLYHEDRON EQUATION AND A SIMPLIFIED TECHNIQUE FOR FINDING THIS SET
ELK, SB
[J]. JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1984, 24 (04): : 203 - 206
[6] RING PERCEPTION - A NEW ALGORITHM FOR DIRECTLY FINDING THE SMALLEST SET OF SMALLEST RINGS FROM A CONNECTION TABLE
FAN, BT
PANAYE, A
DOUCET, JP
BARBU, A
[J]. JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1993, 33 (05): : 657 - 662
[7] HOROWITZ E, 1984, FUNDAMENTALS DATA ST
[8] ENHANCED ALGORITHM FOR FINDING THE SMALLEST SET OF SMALLEST RINGS
QIAN, C
FISANICK, W
HARTZLER, DE
CHAPMAN, SW
[J]. JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1990, 30 (02): : 105 - 110
[9] ALGORITHM FOR FINDING SMALLEST SET OF SMALLEST RINGS
ZAMORA, A
[J]. JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1976, 16 (01): : 40 - 43

← 1 →