We have developed efficient parameterized algorithms for the enumeration problems of graphs arising in chemistry. In particular, we have focused on the following problems: enumeration of Kekul\'e structures, computation of Hosoya index, computation of Merrifield-Simmons index, and computation of graph entropy based on matchings and independent sets. All these problems are known to be $\# P$-complete. We have developed FPT algorithms for bounded treewidth and bounded pathwidth for these problems with a better time complexity than the known state-of-the-art in the literature. We have also conducted experiments on the entire PubChem database of chemical compounds and tested our algorithms. We also provide a comparison with naive baseline algorithms for these problems, along with a distribution of treewidth for the chemical compounds available in the PubChem database.
翻译:----
在化学中拓扑指数的参数化算法
我们为化学中出现的图的枚举问题开发了高效的参数化算法。特别地,我们专注于下列问题的计算:Kekul\'e结构的枚举、Hosoya指数的计算、Merrifield-Simmons指数的计算、以及基于匹配和独立集的图熵的计算。所有这些问题都已知是$\# P$-完全的。我们为这些问题的有限树宽和有限路径宽度开发了FPT算法,与文献中已知最新技术相比具有更好的时间复杂度。我们还在PubChem化合物数据库中进行了实验并测试了我们的算法。我们还提供了这些问题的朴素基线算法的比较,以及PubChem数据库中化合物的树宽分布。