In the chemical community the need for representing chemical structures within a given family and of efficiently enumerating these structures suggested the use of computers and the implementation of fast enumeration algorithms. This paper considers the isomeric acyclic structures focusing on the enumeration of the alkane molecular family. For this family, Trinajstic et al. (1991) devised an enumeration algorithm which is the most widely known and utilized nowadays. Kvasnicka and Pospichal (1991) have proposed an algorithmic scheme which, from the computational complexity point of view, can prove to be more efficient than the Trinajstic one, nevertheless, this algorithm, to the best of our knowledge, has never been implemented. Indeed an efficient implementation requires the introduction of non trivial data structures and other computational tricks. The main contribution of this paper consists of the definition of the implementation details of Kvasnicka-Pospichal's algorithm, in a comparison of Trinajstic's, Kvasnicka-Pospichal's and two new algorithms, proposed here, in terms of both computational complexity analysis and running times.

Chemical Trees Enumeration Algorithms

ARINGHIERI, ROBERTO;
2003-01-01

Abstract

In the chemical community the need for representing chemical structures within a given family and of efficiently enumerating these structures suggested the use of computers and the implementation of fast enumeration algorithms. This paper considers the isomeric acyclic structures focusing on the enumeration of the alkane molecular family. For this family, Trinajstic et al. (1991) devised an enumeration algorithm which is the most widely known and utilized nowadays. Kvasnicka and Pospichal (1991) have proposed an algorithmic scheme which, from the computational complexity point of view, can prove to be more efficient than the Trinajstic one, nevertheless, this algorithm, to the best of our knowledge, has never been implemented. Indeed an efficient implementation requires the introduction of non trivial data structures and other computational tricks. The main contribution of this paper consists of the definition of the implementation details of Kvasnicka-Pospichal's algorithm, in a comparison of Trinajstic's, Kvasnicka-Pospichal's and two new algorithms, proposed here, in terms of both computational complexity analysis and running times.
2003
4OR
1(1)
67
83
http://www.springerlink.com/content/111812/
Exact enumeration problems; generating functions; trees; enumeration of graphs and maps; applications
Aringhieri, Roberto; Hansen, P.; Malucelli, F.
File in questo prodotto:
File Dimensione Formato  
2003-ChemicalTreesEnumerationAlgorithms.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 139.53 kB
Formato Adobe PDF
139.53 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2003-ChemicalTreesEnumerationAlgorithms-PostPrint.pdf

Open Access dal 01/04/2004

Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 631.58 kB
Formato Adobe PDF
631.58 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/55616
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 11
social impact