  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.
