On finding nonisomorphic connected subgraphs and distinct molecular substructures.
Publikation: Beiträge in Zeitschriften › Zeitschriftenaufsätze › Forschung › begutachtet
Standard
in: Journal of Chemical Information and Computer Science, Jahrgang 41, Nr. 2, 03.2001, S. 314-320.
Publikation: Beiträge in Zeitschriften › Zeitschriftenaufsätze › Forschung › begutachtet
Harvard
APA
Vancouver
Bibtex
}
RIS
TY - JOUR
T1 - On finding nonisomorphic connected subgraphs and distinct molecular substructures.
AU - Rücker, Gerta
AU - Rücker, Christoph
PY - 2001/3
Y1 - 2001/3
N2 - The problem of finding all nonisomorphic subgraphs of a given graph (all distinct substructures of a given molecular structure) is discussed. A computer program is introduced that first generates all connected subgraphs and then uses a combination of well-discriminating graph invariants to eliminate duplicates. The program is broadly applicable, in particular for molecular graphs which may or may not contain unsaturation or heteroatoms. The number of distinct substructures (N s), proposed earlier as a measure of a compound's complexity which takes into account its symmetry, is thus automatically obtained. As was to be expected, due to the nature of the problem the computational effort increases exponentially with problem size, whence in most cases complexity measures other than N s are to be preferred.
AB - The problem of finding all nonisomorphic subgraphs of a given graph (all distinct substructures of a given molecular structure) is discussed. A computer program is introduced that first generates all connected subgraphs and then uses a combination of well-discriminating graph invariants to eliminate duplicates. The program is broadly applicable, in particular for molecular graphs which may or may not contain unsaturation or heteroatoms. The number of distinct substructures (N s), proposed earlier as a measure of a compound's complexity which takes into account its symmetry, is thus automatically obtained. As was to be expected, due to the nature of the problem the computational effort increases exponentially with problem size, whence in most cases complexity measures other than N s are to be preferred.
KW - Chemistry
UR - http://www.scopus.com/inward/record.url?scp=0035272501&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/688d9fc6-5d8a-335a-9129-5946ab42687d/
U2 - 10.1021/ci000092b
DO - 10.1021/ci000092b
M3 - Journal articles
VL - 41
SP - 314
EP - 320
JO - Journal of Chemical Information and Computer Science
JF - Journal of Chemical Information and Computer Science
SN - 0095-2338
IS - 2
ER -