TY  - JOUR
T1  - New Adaptive Matching Order and Performance Comparison for Subgraph Matching Problem
AU  - Min, Seunghwan 
AU  - Shin, Wonseok 
AU  - Kim, Chaewon 
AU  - Park, Kunsoo 
JO  - Journal of KIISE, JOK
PY  - 2022
DA  - 2022/1/14
DO  - 10.5626/JOK.2022.49.1.1
KW  - graph analysis
KW  - subgraph matching
KW  - matching order
KW  - adaptive matching order
AB  - In recent years, graph analysis has been used in various applications. One of the fundamental problems in graph analysis is the subgraph matching problem. Given a data graph and a query graph, the subgraph matching problem is to find all embeddings of the query graph in the data graph. Many backtracking-based algorithms have been studied to solve this problem. In this paper, we analyzed the problems in adaptive matching order proposed by DAF, a state-of-the-art algorithm that solves this problem, and introduced an improved adaptive matching order. Furthermore, we conducted experiments with real data graphs to demonstrate that the proposed matching order was more effective than the previous matching orders if the pruning technique was not used or the elapsed time was not very short even if the pruning technique was used.