Branch-and-bound algorithms for enumerating treelike chemical graphs with given path frequency using detachment-cut.

Area of Science:

• Chemoinformatics
• Computational Chemistry
• Graph Theory

Background:

• Computational methods for enumerating chemical graphs are crucial for applications like novel compound structure determination.
• Fujiwara et al. developed an efficient branch-and-bound algorithm for enumerating treelike chemical graphs.

Purpose of the Study:

• To augment Fujiwara et al.'s algorithm for chemical graph enumeration.
• To reduce the search space within the branch-and-bound framework using a new bounding operation.

Main Methods:

• Introduction of a novel bounding operation termed 'detachment-cut'.
• Augmentation of the existing branch-and-bound algorithm by Fujiwara et al.
• Implementation of the enhanced algorithm in a freely accessible web server.

Main Results:

• The proposed algorithm demonstrates improved performance in computation time compared to Fujiwara et al.'s method.
• Experimental results on chemical compound data validate the efficiency gains.
• The enhanced algorithm effectively reduces the search space.

Conclusions:

• The detachment-cut bounding operation significantly enhances the efficiency of treelike chemical graph enumeration.
• The developed algorithm offers a faster computational approach for chemoinformatics applications.
• A web-based implementation provides accessible utility for researchers.