I/O Efficient Algorithm for Graph Pattern Matching Problem
P. Solai Rani, Abhishek Srivastava · 2012
This paper presents an I/O efficient algorithm for graph pattern matching problem. It is based on decision tree approach proposed by B. T. Messmer and H. Bunke. In that paper, if the time needed for preprocessing is neglected, the computational complexity of their approach is only polynomial in the number of input graph vertices. However, the decision tree is of exponential size. It's not practical for the graphs with large size.. In the new algorithm, we increases the preprocessing time as well as space complexity, it can remarkably reduces the number of I/Os and keeps the same time complexity. The algorithm is improved here to reduce its I/O complexity and to achieve a better performance on large graphs.