I/O Efficient Algorithm for Graph Pattern Matching Problem

Full Text(PDF, ) PP.434450


Author(s) 
Pushpi Rani, Abhishek Srivastava 

KEYWORDS 
Decision tree; Graph isomorphism; Subgraph isomorphism; I/O complexity; Adjacency matrix; Permutation matrix; 

ABSTRACT 
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 

References 

[1] A.Aggarwal and J. S.Vitter (1988). The input/output complexity of
sorting and related problems.Commun. ACM, 31(9):1116–1127.
[2] Ashay Dharwadker and Shariefuddin Pirzada (2008.) Graph
Theory, Orient Longman and Universities Press of India,
[3] Jeffrey Scott Vitter (2008) Algorithms and Data Structures for
External Memory
[4] B.T. Messmer*, H. Bunke (1999). A decision tree approach to
graph and subgraph isomorphism detection, Pattern Recognition
32 19791998.
[5] J. S. Vitter and E. A. M. Shriver, [1994] “Algorithms for parallel
memory I: Twolevel memories,” Algorithmica, vol. 12, no. 2–3,
pp. 110–147
[6] JohnTagore Tevet (2008), Constructive Representation of
Graphs: A Selection of Examples, S.E.R.R., Tallinn.


