.png){kind=icon}
Return
Finding Maximum Common Subgraphs Efficiently Through Dynamic Bidirectional Vertex Selection
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-5719-6_3.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Finding the Maximum Common Subgraph (MCS) in two graphs is NP-hard, and MCS algorithms adopt heuristics to improve time performance. In particular, the state-of-the-art branch-and-bound MCS algorithms, including McSplit, McSplit+RL, McSplit+LL, and McSplit+DAL, apply heuristics in selecting vertices to match from the two input graphs. However, they always select a vertex from the first graph to match with a set of candidate vertices from the second graph. This fixed order of the two graphs is not necessarily the best, because the number of candidates for a single vertex may vary. Therefore, we propose a bidirectional vertex selection method in which each time a single vertex is dynamically selected from either the first or the second graph depending on the number of candidate vertices to match in the other graph. This way the search space is reduced and the search time performance is improved. We have evaluated our method on a real-world chemical molecular graph dataset as well as other datasets. The results show that our proposed approach can find more non-trivial MCS than the best of McSplit family algorithms.
Keywords:
Data mining
Exact algorithms
Maximum Common Subgraph
Journal
W
IF:
0
Papers:
32
Citations:
0
Organization
Cited Papers
A note on the derivation of maximal common subgraphs of two directed or undirected graphs.png)
Calcolo
CalcoloIF0
PREAI
ShareSaveShareSave
ShareSave
View more