Structured Graph Decomposition Towards Proficient Exact Subgraph Matching

Abstract

Structures that can be represented as graphs are based on graph theory. Graph databases apply graph theory to store information about the relationships between entries in terms of graphs. The study of graph decomposition has been one of the most important topics in graph theory and also plays an important role in the study of the combinatorics of experimental designs. The main idea of graph decomposing is that matching the smaller graph structure is easier and results in low complexity than matching the original large graph. In this paper, we propose the graph decomposition algorithm based on edge-based representation of the undirected connected graph to obtain its decomposed subgraphs. Finally, we conduct an extensive set of experiments on different type of graphs to demonstrate the efficiency of our approach for further efficient exact subgraph matching.