DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Park, Sung-Soo | - |
dc.contributor.advisor | 박성수 | - |
dc.contributor.author | Jeong, Young-Yun | - |
dc.contributor.author | 정영윤 | - |
dc.date.accessioned | 2011-12-14T04:10:19Z | - |
dc.date.available | 2011-12-14T04:10:19Z | - |
dc.date.issued | 2010 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=455165&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/40885 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 산업및시스템공학과, 2010.08, [ iii, 54 p. ] | - |
dc.description.abstract | In this thesis, we consider the maximum common subtree problem (MCST) which can be a notion of graph similarity. The MCST problem is defined as follows. Given two graphs $G_1 = (V_1, E_1)$ and $G_{2} = (V_{2}, E_{2})$ with $|V_1|=|V_2|$ , find subgraphs of $G_1$ and $G_2$ having tree structure which are isomorphic with the maximum number of edges. To solve this problem, we use the property of the degree sequence equivalence between two graphs, which means that the two graphs have the same degree sequences when they are isomorphic. First, we define the maximum degree sequence equivalence subgraph problem and propose a 0-1 integer programming formulation for this problem. Our algorithm uses this formulation to detect the degree sequence equivalent subgraphs having tree structure. This formulation contains the conditional constraints having big-M coefficients to represent the degree equivalence of matched pair of nodes. Hence, the formulation becomes hard to solve for large instances. To deal with this, we apply the decomposition technique and combinatorial Benders’ cuts proposed by Codato and Fischetti (2006). Moreover, we also implement the cutting plane method to handle the exponential number of constraints related to the sub-tour elimination inequalities. After we find the two trees, our algorithm checks whether detected trees are isomorphic or not. The tree isomorphism is checkable by the AHU-algorithm in polynomial time. Overall algorithm recursively solve the formulation until isomorphic two graphs are detected. Otherwise, our algorithm solves the formulation again after excluding current solution. Computational results show that this algorithm performs relatively well in solving of random instances of moderate size compared to the earlier integer programming model for the maximum common edge subgraph problem. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | degree sequence | - |
dc.subject | integer programming | - |
dc.subject | common subtree | - |
dc.subject | common subgraph | - |
dc.subject | combinatorial Benders` cut | - |
dc.subject | 조합적 Benders의 절단 평면 | - |
dc.subject | 차수열 | - |
dc.subject | 정수 계획법 | - |
dc.subject | 공통 부분 트리 | - |
dc.subject | 공통 부분 그래프 | - |
dc.title | (An) algorithm for the maximum common subtree problem using the degree sequence | - |
dc.title.alternative | 그래프 마디의 차수열을 이용한 최대 공통 부분트리 문제의 해법 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 455165/325007 | - |
dc.description.department | 한국과학기술원 : 산업및시스템공학과, | - |
dc.identifier.uid | 020084121 | - |
dc.contributor.localauthor | Park, Sung-Soo | - |
dc.contributor.localauthor | 박성수 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.