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 [J].

BALDUCCI, R ;

PEARLMAN, RS .

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 [J].

DOWNS, GM ;

GILLET, VJ ;

HOLLIDAY, JD ;

LYNCH, MF .

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 [J].

ELK, SB .

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 [J].

FAN, BT ;

PANAYE, A ;

DOUCET, JP ;

BARBU, A .

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 [J].

QIAN, C ;

FISANICK, W ;

HARTZLER, DE ;

CHAPMAN, SW .

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1990, 30 (02) :105-110

[9] ALGORITHM FOR FINDING SMALLEST SET OF SMALLEST RINGS [J].

ZAMORA, A .

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1976, 16 (01) :40-43

← 1 →