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

Recently viewed

Publications

  1. Probabilistic approach to modelling of recession curves
  2. The role of learners’ memory in app-based language instruction: the case of Duolingo.
  3. Teachers’ use of data from digital learning platforms for instructional design
  4. Q-Adaptive Control of the nonlinear dynamics of the cantilever-sample system of an Atomic Force Microscope
  5. Early Detection of Faillure in Conveyor Chain Systems by Wireless Sensor Node
  6. Explaining and controlling for the psychometric properties of computer-generated figural matrix items
  7. Early subtropical forest growth is driven by community mean trait values and functional diversity rather than the abiotic environment
  8. Influences of RVE topology, discretization and boundary conditions in practical multiscaling - a comparison
  9. I&EC 18-Small particle size magnesium in one-pot Grignard-Zerewitinoff reactions: Kinetics of and practical application to reductive dechlorination of persistent organic pollutants
  10. Introduction to Felipe Ehrenberg's "In Search of a Model for Life"
  11. Modeling Individual Differences in Children’s Information Integration During Pragmatic Word Learning
  12. Grüne Parteien
  13. On-board pneumatic pressure generation methods for soft robotics applications
  14. I Am Not A Hacker
  15. Robust and Optimal Control Designed for Autonomous Surface Vessel Prototypes
  16. Points of cooperation: integrating cooperative learning into web-based courses
  17. Health State Valuation Methods and Reference Points
  18. Decoding evidence-based entrepreneurship
  19. Using a Bivariate Polynomial in an EKF for State and Inductance Estimations in the Presence of Saturation Effects to Adaptively Control a PMSM
  20. Load, Release and Fire
  21. Trans pixelate substitution scheme for denoising computed tomography images towards high diagnosis accuracy
  22. Thinking and Diagrams - An Introduction
  23. Modeling of a thermomechanical process chain for sheet steels
  24. Water and soil towards sustainable land use
  25. The new zeppelin university translation of weber's 'class, status, party'
  26. Time and Income Poverty – An Interdependent Multidimensional Poverty Approach with German Time Use Diary Data
  27. International Master’s Programme in Sustainable Development and Management
  28. Missiology: An Introduction to the Foundations, History, and Strategies of World Missions