论文标题
最大共同（连接）子图问题的加强分支和结合算法
A Strengthened Branch and Bound Algorithm for the Maximum Common (Connected) Subgraph Problem
论文作者
论文摘要
我们提出了一种基于两个新的操作员，长短记忆（LSM）和Leaf Vertex Union Match（LUM）的最大常见（连接）诱导子图问题，提出了一种新的且增强的分支和结合（BNB）算法。给定两个图表，我们使用第一个图的每个顶点的短期奖励以及两个图表的每个顶点奖励的每个顶点的短期奖励，搜索了最大通用（连接）诱导子图的最大（连接）诱导子图。通过这种方式，BNB过程学会了大大减少搜索树的大小并改善算法性能。 Lum的第二个操作员通过同时匹配连接到当前匹配的顶点的叶顶点来进一步提高性能，并允许该算法匹配多个顶点对，而不会影响解决方案最佳性。我们将两个运算符纳入最新的BNB算法MCSPLIT中，并将所得算法表示为McSplit+ll。实验表明，MCSPLIT+LL胜过MCSPLIT+RL，这是MCSPLIT的最新变体，使用了比MCSPLIT优越的增强学习。
We propose a new and strengthened Branch-and-Bound (BnB) algorithm for the maximum common (connected) induced subgraph problem based on two new operators, Long-Short Memory (LSM) and Leaf vertex Union Match (LUM). Given two graphs for which we search for the maximum common (connected) induced subgraph, the first operator of LSM maintains a score for the branching node using the short-term reward of each vertex of the first graph and the long-term reward of each vertex pair of the two graphs. In this way, the BnB process learns to reduce the search tree size significantly and improve the algorithm performance. The second operator of LUM further improves the performance by simultaneously matching the leaf vertices connected to the current matched vertices, and allows the algorithm to match multiple vertex pairs without affecting the solution optimality. We incorporate the two operators into the state-of-the-art BnB algorithm McSplit, and denote the resulting algorithm as McSplit+LL. Experiments show that McSplit+LL outperforms McSplit+RL, a more recent variant of McSplit using reinforcement learning that is superior than McSplit.
