A two-stage discrete optimization method for largest common subgraph problems

Nobuo Funabiki, Junji Kitamichi


7 被引用数 (Scopus)


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 = (V1, E1) and H = (V2. E2), 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),/(w)} ∈ 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
出版ステータスPublished - 1999

ASJC Scopus subject areas

  • ソフトウェア
  • ハードウェアとアーキテクチャ
  • コンピュータ ビジョンおよびパターン認識
  • 電子工学および電気工学
  • 人工知能


「A two-stage discrete optimization method for largest common subgraph problems」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。