On finding nonisomorphic connected subgraphs and distinct molecular substructures.
Research output: Journal contributions › Journal articles › Research › peer-review
Authors
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.
Translated title of the contribution | Auf der Suche nach nichtisomorphen verbundenen Subgraphen und eindeutigen molekularen Substrukturen. |
---|---|
Original language | English |
Journal | Journal of Chemical Information and Computer Science |
Volume | 41 |
Issue number | 2 |
Pages (from-to) | 314-320 |
Number of pages | 7 |
ISSN | 0095-2338 |
DOIs | |
Publication status | Published - 03.2001 |
Externally published | Yes |
- Chemistry