Premium
Fast algorithm for ring perception
Author(s) -
Matyska Luděk
Publication year - 1988
Publication title -
journal of computational chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.907
H-Index - 188
eISSN - 1096-987X
pISSN - 0192-8651
DOI - 10.1002/jcc.540090503
Subject(s) - algorithm , computer science , extension (predicate logic) , ring (chemistry) , graph , set (abstract data type) , theoretical computer science , chemistry , organic chemistry , programming language
An algorithm for finding rings in graphs is presented. The algorithm is based on the Welch‐Assembly‐Gibbs algorithm of Wipke and Dyott but using the homeomorphically reduced pruned graph (the extension of HRG of Balaban et al). The algorithm is able to generate both the fundamental set of rings and all possible rings in a given graph. The time and storage needs are superior to both underlying algorithms. The CPU times of the old and new algorithms are given.