EECS Publication
A New Approach and Faster Exact Methods for the Maximum Common Subgraph Problem
W. Henry Suters, Faisal N. Abu-Khzam, Yun Zhang, Christopher T. Symons, Nagiza F. Samatovak and Michael A. Langston
The Maximum Common Subgraph (MCS) problem appears in many guises and in a wide variety of applications. The usual goal is to take as inputs two graphs, of order m and n, respectively, and find the largest induced subgraph contained in both of them. MCS is frequently solved by reduction to the problem of finding a maximum clique in the order mn association graph, which is a particular form of product graph built from the inputs. In this paper a new algorithm, termed 'clique branching,' is proposed that exploits a special structure inherent in the association graph. This structure contains a large number of naturally-ordered cliques that are present in the association graph's complement. A detailed analysis shows that the proposed algorithm requires O((m + 1)n) time, which is a superior worst-case bound to those known for previously-analyzed algorithms in the setting of the MCS problem.
Published 2005-11-05 05:00:00 as ut-cs-05-568 (ID:170)