Subgraph Isomorphism Algorithms for Matching Graphs: A Survey

Ms. Rachna Somkunwar, Dr. Vinod Moreshwar Vaze

Abstract


This paper provides a review of subgraph isomorphism
algorithms for graph matching. In computer vision,
pattern matching is one of the most popular areas for matching
tokens. Rather than example acknowledgment, the match as
a rule must be correct. The pattern may include graph, tree
structure or any sequences. The methods of matching subgraph
include size and types of graphs. An overview of different
methods of subgraph isomorphism is also presented here. The
main objective of this paper is to provide comparative study of
existing algorithms.


Full Text:

PDF

References


D.H. Rouvray, A.T. Balaban, ” Chemical applications of graph theory”,

in: R.J. Wilson, L.W. Beineke (Eds.), Applications of Graph Theory,

Academic Press, New York, pp. 177-221, 1979. .

H. Ehrig, ”Introduction to graph grammers with applications to semantic

networks”, Comput. Math. Appl. , 557-572, 1992.

S.W. Lu, Y. Ren, C.Y. Suen, ” Hierarchical attributed graph representation

and recognition of handwritten Chinese characters”, Pattern Recognition

, 617-632, 1991..

H. Bunke, G. Allerman, ” Inexact graph matching for structural pattern

recognition”, Pattern Recognition Lett. 1 245-253,1983.

S.W. Lee, J.H. Kim, F.C.A. Groen, ” Translation-rotation and scale

invariant recognition of hand-drawn symbols in schematic diagrams”, Int.

J. Pattern Recognition Artif. Intelligence,1-15,1990.

S.W. Lee, J.H. Kim, ” Attributed stroke graph matching for seal imprint

verification”, Pattern Recognition Lett. 137-145, 1989.

Garey, M.R., Johnson, ”D.S.: Computers and Intractability; A Guide to

the Theory of NP-Completeness”, W. H. Freeman and Co, New York,USA

(1990).

vanWyk, Barend J., and Michael A. van Wyk. ”A pocs-based graph

matching algorithm”, IEEE transactions on pattern analysis and machine

intelligence,pp. 1526-1530,2004.

Dovier, A., and Piazza, C. ” The subgraph bisimulation problem”,IEEE

Transactions on Knowledge and Data Engineering, pp.1055-1056,2003.

Chen, A. C. L., Elhajj, A., Gao, S., Sarhan, A., Afra, S., Kassem, A.,

and Alhajj, R ”Approximating the Maximum Common Subgraph Isomorphism

Problem with a Weighted Graph”, Knowledge-Based Systems.

Messmer, B. T., and Bunke, H. ” A new algorithm for error-tolerant

subgraph isomorphism detection”, Pattern Analysis and Machine Intelligence,

IEEE Transactions on, 20(5), 493-504,1998.

Messmer, B. T., and Bunke, H. ” A decision tree approach to graph

and subgraph isomorphism detection”, Pattern recognition, 32(12), 1979-

Cordella, L. P., Foggia, P., Sansone, C.,and Vento, M. ”A (sub) graph

isomorphism algorithm for matching large graphs”, Pattern Analysis and

Machine Intelligence, IEEE Transactions on, 26(10),1367-1372,2004.

DePiero, F., and Krout, D. ”An algorithm using length-r paths to

approximate subgraph isomorphism”, Pattern recognition letters, 24(1),

-46,2003.

Zhang, Shijie, Shirong Li, and Jiong Yang. ”GADDI: distance index

based subgraph matching in biological networks.” Proceedings of the 12th

International Conference on Extending Database Technology: Advances

in Database Technology. ACM, 2009.

Plantenga, Todd. ”Inexact subgraph isomorphism in MapReduce.” Journal

of Parallel and Distributed Computing ,164-175,2013.

Schmidt, Douglas C., and Larry E. Druffel. ”A fast backtracking algorithm

to test directed graphs for isomorphism using distance matrices.”

Journal of the ACM (JACM, 433-445,1976.

Zhang, Shijie, Shirong Li, and Jiong Yang. ”SUMMA: subgraph matching

in massive graphs.” Proceedings of the 19th ACM international

conference on Information and knowledge management.ACM, 2010.

Di Natale, Raffaele, et al. ”Sing: Subgraph search in non-homogeneous

graphs.” BMC bioinformatics , 2010.

Klein, Karsten, Nils Kriege, and Petra Mutzel. ”CT-index: Fingerprintbased

graph indexing combining cycles and trees.” Data Engineering

(ICDE), 2011 IEEE 27th International Conference on. IEEE, 2011.

He, Huahai, and Ambuj K. Singh. ”Closure-tree: An index structure for

graph queries.” Data Engineering, 2006. ICDE’06. Proceedings of the

nd International Conference on. IEEE, 2006.

Dahm, Nicholas, et al. ”Efficient subgraph matching using topological

node feature constraints.” Pattern Recognition 48.2 (2015): 317-330.

Qiu, Jing, Xiaohong Su, and Peijun Ma. ”Using reduced execution flow

graph to identify library functions in binary code.” IEEE Transactions on

Software Engineering ,187-202,2016.

Lischka, Jens, and Holger Karl. ”A virtual network mapping algorithm

based on subgraph isomorphism detection.” Proceedings of the 1st ACM

workshop on Virtualized infrastructure systems and architectures. ACM,

Zheng, Weiguo, et al. ”SQBC: An efficient subgraph matching method

over large and dense graphs.” Information Sciences , 116-131, 2014.

Ullmann, Julian R. ”An algorithm for subgraph isomorphism.” Journal

of the ACM (JACM) 23.1 31-42, 1976.

B.D. McKay, Practical Graph Isomorphism, Congressus Numerantium,

vol. 30, pp. 45-87, 1981

H. Bunke and B.T. Messmer, Efficient Attributed Graph Matching and

Its Application to Image Analysis, Proc. Image Analysis and Processing,

pp. 45- 55, 1995.

W.J. Christmas, J. Kittler, and M. Petrou, Structural Matching in

Computer Vision Using Probabilistic Relaxation, IEEE Trans. Pattern

Analysis and Machine Intelligence, vol. 17, no. 8, pp. 749-764, 1995.

Cordella, Luigi P., et al. and quot;Performance evaluation of the VF

graph matching algorithm.and quot; Image ,Analysis and Processing,

Proceedings. International Conference on. IEEE, 1999.

Cordella, Luigi P.,et al. ”A (sub) graph isomorphism algorithm for

matching large graphs.” IEEE transactions on pattern analysis and machine

intelligence , 1367-1372, 2004.


Refbacks

  • There are currently no refbacks.


Copyright © IJETT, International Journal on Emerging Trends in Technology