Using Branch Learning to Optimize the Search for Subgraph Isomorphism
Subgraph isomorphism problem is a classic and widely applicable NP complete problem.A hybrid branch learning strategy(SIBL)is proposed to reduce the solution time by combining solveless records and vertex degree constraint rules,in order to address the issue of high computational cost and dependence on vertex degree in precise algorithms.No solution record refers to the branch path without a target solution before each restart of the algorithm.In order to remove invalid searches,candidate vertices in the target graph with a vertex degree smaller than the current pattern graph vertex are first removed,and then vertices that appear in the no solution record are removed.Finally,descend-ing sorting is performed based on the vertex score,with priority given to selecting vertices with higher scores.The new strategy provides two score calculation methods that utilize the upper bound descent to calculate a single vertex and vertex matching pairs,and alternately use the two scores to select branch vertices to quickly find the target solution,avoiding the local optimal problem of greedy selection.Through testing 14 220 examples from fields such as biology and imaging,it was found that SIBL is superior to the current leading Glasgow,McSplit+RL_SI solved 10.08％and 19.88％of moderately difficult cases respectively,verifying that branch learning can effectively improve the solving effi-ciency of subgraph isomorphism algorithms.
万方数据
维普
