作者：Giovanna K. Conrado Amir K. Goharshady Harshit J. Motwani Sergei Novozhilov
我们已经为化学中出现的图的枚举问题开发了有效的参数化算法。特别是，我们关注了以下问题：Kekul结构的枚举、Hosoya指数的计算、Merrifield Simmons指数的计算以及基于匹配和独立集的图熵的计算。所有这些问题都是$\#P$完备的。我们已经为这些问题开发了有界树宽度和有界路径宽度的FPT算法，其时间复杂度比文献中已知的最先进技术要好。我们还对PubChem的整个化合物数据库进行了实验，并测试了我们的算法。我们还为这些问题提供了与天真基线算法的比较，以及PubChem数据库中可用的化合物的树宽分布。
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.
论文链接：http://arxiv.org/pdf/2303.13279v1
更多计算机论文：http://cspaper.cn/