On finding nonisomorphic connected subgraphs and distinct molecular substructures.

Research output: Journal contributionsJournal articlesResearchpeer-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 contributionAuf der Suche nach nichtisomorphen verbundenen Subgraphen und eindeutigen molekularen Substrukturen.
Original languageEnglish
JournalJournal of Chemical Information and Computer Science
Volume41
Issue number2
Pages (from-to)314-320
Number of pages7
ISSN0095-2338
DOIs
Publication statusPublished - 03.2001
Externally publishedYes

DOI