A New Approach and Faster Ezact Methods for the Mazimum Common Subgraph Problem
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 graphs 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.
W. Henry Suters Faisal N. Abu-Khzam Yun Zhang Christopher T. Symons Nagiza F. Samatova Michael A. Langston
Department of Mathematics and Computer Science, Carson-Newman College CN Box 71958, Jefferson City, Division of Computer Science and Mathematics, Lebanese American University Beirut, Lebanon Department of Computer Science, University of Tennessee Knoxville, TN 37996-3450, USA Computer Science and Mathematics Division, Oak Ridge National Laboratory P.O. Box 2008, Oak Ridge, T
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
717-727
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）