On finding nonisomorphic connected subgraphs and distinct molecular substructures.

Research output: Journal contributionsJournal articlesResearchpeer-review

Standard

On finding nonisomorphic connected subgraphs and distinct molecular substructures. / Rücker, Gerta; Rücker, Christoph.
In: Journal of Chemical Information and Computer Science, Vol. 41, No. 2, 03.2001, p. 314-320.

Research output: Journal contributionsJournal articlesResearchpeer-review

Harvard

APA

Vancouver

Bibtex

@article{efa7865faab84c9690fa6b6211729e21,
title = "On finding nonisomorphic connected subgraphs and distinct molecular substructures.",
abstract = "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. ",
keywords = "Chemistry",
author = "Gerta R{\"u}cker and Christoph R{\"u}cker",
year = "2001",
month = mar,
doi = "10.1021/ci000092b",
language = "English",
volume = "41",
pages = "314--320",
journal = "Journal of Chemical Information and Computer Science",
issn = "0095-2338",
publisher = "American Chemical Society",
number = "2",

}

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 -

DOI