Subgraph Isomorphism Algorithms for Matching Graphs: A Survey
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:
PDFReferences
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