AN ALGORITHM FOR THE MULTIPLE COMMON SUBGRAPH PROBLEM

The multiple largest common subgraph (MLCS) problem is presented, and a new algorithm and its implementation to solve this problem are described. The method consists of using a largest common subgraphs algorithm (LCSA) and a maximal common subgraphs algorithm (SUPLIMIT) that is a modification of LCSA. Because the largest common subgraph problem is a polynomial problem for trees, LCSA explores the spanning trees of the graphs and uses a backtracking method to be exhaustive in its search. A heuristic in LCSA gives numbers to the nodes of each graph such that nodes having a smaller number are more likely to be in a solution. LCSA, together with SUPLIMIT, is used in a series of pairwise graph comparisons to solve the MLCS problem. A preprocessing function is used to find a lower bound for the size of solutions to this problem. This improves the efficiency of the algorithm.