
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A TwoStage Discrete Optimization Method for Largest Common Subgraph Problems
Nobuo FUNABIKI Junji KITAMICHI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E82D
No.8
pp.11451153 Publication Date: 1999/08/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: common subgraph, isomorphic, NPcomplete, greedy method, discrete descent method, simulated annealing,
Full Text: PDF>>
Summary:
A novel combinatorial optimization algorithm called 2stage discrete optimization method (2DOM) is proposed for the largest common subgraph problem (LCSP) in this paper. Given two graphs G=(V_{1}, E_{1}) and H=(V_{2}, E_{2}), the goal of LCSP is to find a subgraph G'=(V_{1}', E_{1}') of G and a subgraph H'=(V_{2}', E_{2}') of H such that G' and H' are not only isomorphic to each other but also their number of edges is maximized. The two graphs G' and H' are isomorphic when V_{1}'=V_{2}' and E_{1}'=E_{2}', and there exists onetoone vertex correspondence f: V_{1}' V_{2}' such that {u, v} E_{1}' if and only if{f(u), f(v)} E_{2}'. LCSP is known to be NPcomplete in general. The 2DOM consists of a construction stage and a refinement stage to achieve the high solution quality and the short computation time for large size difficult combinatorial optimization problems. The construction stage creates a feasible initial solution with considerable quality, based on a greedy heuristic method. The refinement stage improves it keeping the feasibility, based on a random discrete descent method. The performance is evaluated by solving two types of randomly generated 1200 LCSP instances with a maximum of 500 vertices for G and 1000 vertices for H. The simulation result shows the superiority of 2DOM to the simulated annealing in terms of the solution quality and the computation time.

