论文标题
给定路径频率规格满足两个分离周期的枚举化学图
Enumerating Chemical Graphs with Two Disjoint Cycles Satisfying Given Path Frequency Specifications
论文作者
论文摘要
满足给定约束的满足化学图是数学和计算化学中的一个基本问题，并且在最近提出的反向QSAR/QSPR的框架中起着至关重要的作用。在本文中，约束是由特征向量给出的，每个特征向量由给定路径中的路径频率组成。我们考虑了满足路径频率约束的枚举化学图的问题，这些化学图由一对特征向量给出，这些特征向量指定了每个路径频率的上限和下限。我们设计了一种分支结合的算法，用于枚举双块2凸出结构的化学图，即包含两个边缘循环的图。我们通过实施我们提出的算法进行了一些计算实验。
Enumerating chemical graphs satisfying given constraints is a fundamental problem in mathematical and computational chemistry, and plays an essential part in a recently proposed framework for the inverse QSAR/QSPR. In this paper, constraints are given by feature vectors each of which consists of the frequencies of paths in a given set of paths. We consider the problem of enumerating chemical graphs that satisfy the path frequency constraints, which are given by a pair of feature vectors specifying upper and lower bounds of the frequency of each path. We design a branch-and-bound algorithm for enumerating chemical graphs of bi-block 2-augmented structure, that is, graphs that contain two edge-disjoint cycles. We present some computational experiments with an implementation of our proposed algorithm.
