مساله ي يافتن زير گراف مشترك ماكزيمم

چكيده انگليسي :

Maximum Common Subgraph Problem Effat Hashemi e hashemi@math iut ac ir September 18 2018 Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Dr Behnaz Omoomi bomoomi@cc iut ac irAdvisor Dr Hamed Fahimi hamed fahimi1@gmail com2010 MSC 05C85 05C90 Keywords Maximum common subgraph Maximum common induced subgraph Maximum common edge subgraph Abstract This M Sc thesis is based on the following papers Challenging complexity of maximum com C D F P V M mon subgraph detection algorithms A performance analysis of three algorithms on a wide database of graphs Journal of Graph Algorithms and Application 11 2007 99 143 On maximum common subgraph problems in K N K F M P series parallel graphs European Journal of Combinatorics 68 2018 79 95G is the maximum common subgraph M CS of two graphs G1 and G2 whenever G is the subgraph of G1 andG2 and there is no common subgraph in G1 and G2 that the number of its vertices is more than G According to thisdefinition M CS is not necessarily unique and usually there are more than one common subgraph for two graphs Although the problem of finding maximum common subgraph is N P complete in general case researchers havetried to simplify it for a family of certain graphs and in some cases they have present some algorithms in polynomialtime In many real world problems it is necessary to compare the objects and determine the degree and composition ofthe similarity between them If the objects and their relations are represented by graphs one of the best methods todetermine the similarity between them is finding the maximum common subgraph of their corresponding graphs Forexample in studying the chemical structure the maximum common subgraph problem in the graphs that model thechemical molecules is used for finding the maximum common structure in the molecules It is noteworthy that M CS problem is a generalization of the induced subgraph isomorphism problem Some prob lems related to M CS are M CIS M CES M CCS and M CDS An induced subgraph is a set S of verticesin graph G and the edges of G with both endpoints in S A graph G is a common induced subgraph of graphs G1and G2 if G is isomorphic to induced subgraphs of G1 and G2 A maximum common induced subgraph M CIS consists of a graph G with the largest number of vertices with this property The maximum common edge subgraph M CES is related to the M CIS An M CES is a subgraph consisting of the largest number of edges commonto both G1 and G2 If the maximum common subgraph is connected then it is represented by M CCS and if themaximum common subgraph is disconnected then it is represented by M CDS In this thesis at first the definitions and concepts that we need are presented In Chapter 2 the three algorithms forfinding maximum common subgraph detection are described In Chapter 3 two applications of the M CS prob lem namely in the pattern recognition and molecular science are presented In Chapter 4 it is proved that theM CCS problem remains N P hard in biconnected series parallel graphs with all vertices of degree three or lessexept one vertex This result is obtained by a polynomial time reduction of the Numerical Matching with TargetSums N M wT S problem Furthermore BBP M CS problem that is the M CS preseving bridgs and cuts is considered in the series parallel graphs and a polynomial time solution is proposed for it This approach yields

هاشمي، عفت

مساله ي يافتن زير گراف مشترك ماكزيمم

زير گراف مشترك ماكزيمم , زير گراف مشترك القايي ماكزيمم , زير گراف مشترك القايي همبند ماكزيمم