A Two - Stage Discrete Optimization Method for Largest Common Subgraph Problems

この論文をさがす

著者

    • FUNABIKI Nobuo
    • the Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University
    • KITAMICHI Junji
    • the Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University

抄録

A novel combinatorial optimization algorithm called 2-stage 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 one-to-one 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 NP-complete 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.

収録刊行物

  • IEICE transactions on information and systems

    IEICE transactions on information and systems 82(8), 1145-1153, 1999-08-25

    一般社団法人電子情報通信学会

参考文献:  20件中 1-20件 を表示

各種コード

  • NII論文ID(NAID)
    110003210164
  • NII書誌ID(NCID)
    AA10826272
  • 本文言語コード
    ENG
  • 資料種別
    ART
  • ISSN
    09168532
  • データ提供元
    CJP書誌  NII-ELS 
ページトップへ