IMPROVED ALGORITHMS FOR ENUMERATING TREE-LIKE CHEMICAL GRAPHS WITH GIVEN PATH FREQUENCY

This paper considers the problem of enumerating all non-isomorphic tree-like chemical graphs with given path frequency, where "tree-like" means that the graph can be viewed as a tree if multiple edges (i.e., edges with the same end points) and a benzene ring are treated as one edge and one vertex, respectively, and "path frequency" is a vector of the numbers of specified vertex-labeled paths that must be realized in every output. This and related problems have several potential applications such as classification of chemical compounds, structure determination using mass-spectrum and/or NMR and design of novel chemical compounds.

For this problem, several studies have been done. Recently, Fujiwara et al. (2008) showed two formulations and for each of them, they gave a branch-and-bound algorithm, which combined efficient enumeration of non-isomorphic trees with bounding operations based on the path frequency and the atom-atom bonds to avoid the generation of invalid trees. In this paper, based on their work and a result of Nagamochi (2006), we introduce two new bounding operations, the detachment-cut and the H-cut, to further reduce the size of the search space. We performed computational experiments to compare our proposed algorithms with those of Fujiwara et al. (2008) using some chemical compound data obtained from the KEGG LIGAND database (http://www.genome.jp/kegg/ligand.html). The results show that our proposed algorithms are much faster than their algorithms.