Branch-and-Bound Algorithms for Enumerating Treelike Chemical Graphs with Given Path Frequency Using Detachment-Cut
Yusuke Ishida, Yuki Kato, Liang Zhao, Hiroshi Nagamochi, Tatsuya Akutsu · Journal of Chemical Information and Modeling · 2010
Computational methods of enumerating chemical graphs have attained great importance in chemoinformatics since they lead to a variety of useful applications including structure determination of novel chemical compounds. Recently, Fujiwara et al. have presented an efficient branch-and-bound algorithm for enumerating treelike chemical graphs with given path frequency. In this paper, we augment Fujiwara et al.'s algorithm by introducing a new bounding operation called detachment-cut to reduce further the search space in the branch-and-bound framework. Experimental results on much chemical compound data show that our proposed algorithm achieves better performance than Fujiwara et al.'s algorithm in computation time. A program that implements our algorithm can be used freely via Web server.