Name
Abstract | ||
|---|---|---|
The maximum common subgraph isomorphism problem is a difficult graph problem, and the problem of finding the maximum common subgraph isomorphism problem is NP-hard. This means there is likely no algorithm that will be able to find the maximal isomorphic common subgraph in polynomial time because as the size of the graphs grows the search space for the solution will grow exponentially. This research provides a method that will approximate the maximum common subgraph isomorphism problem by producing a weighted graph, where the weights will give an indication of the probability that the associated link will be in the maximum common subgraph of the two input graphs. The experimental results show that the method can effectively generate a weighted graph containing most of the expected links that would exist in the maximum common subgraph of some given graphs with similar structures. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.knosys.2015.05.012 | Knowledge-Based Systems |
Keywords | Field | DocType |
Maximum common subgraph,Isomorphism,Weighted graph | Data mining,Mathematical optimization,Combinatorics,Graph isomorphism,Maximum common subgraph isomorphism problem,Computer science,Graph factorization,Induced subgraph isomorphism problem,Distance-hereditary graph,Factor-critical graph,Universal graph,Subgraph isomorphism problem | Journal |
Volume | Issue | ISSN |
85 | C | 0950-7051 |
Citations | PageRank | References |
3 | 0.37 | 28 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alan Chia-Lung Chen | 1 | 4 | 1.05 |
| Ahmad Elhajj | 2 | 26 | 1.89 |
| Shang Gao | 3 | 291 | 59.33 |
| Abdullah Sarhan | 4 | 15 | 3.64 |
| Salim Afra | 5 | 4 | 1.42 |
| Ahmad Kassem | 6 | 3 | 0.37 |
| Reda Alhajj | 7 | 1919 | 205.67 |