A Novel Algorithm Based on the Degree Tree for Graph Isomorphism

Abstract:

The graph isomorphism problem is to study the relationship between two graphs which seem to be different, but essentially identically. A novel algorithm based on the degree tree is proposed, where each node of the tree describes a given vertex and its neighboring information of a graph. Two vertexes in different graphs are regarded as mapping if the corresponding nodes and all their junior nodes are similar. Hence by comparing their degree trees, two graphs can be determined whether matching or not, and the mapping vertexes can be found. Experimental results show the approach’s performance.

• Periodical: Advanced Materials Research (Volumes 225-226)
• Pages: 417-421
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.225-226.417
• Online since: April 2011
• Authors: Long Hao
• Keywords: Degree Tree, Graph Isomorphism, Graph Matching, Pruning Technology

References

[1] D. Conte, P. Foggia, C. Sansone, and M. Vento, Thirty Years of Graph Matching in Pattern Recognition, " Int, l J. Pattern Recognition and Artificial Intelligence, vol. 18, no. 3, pp.265-298, (2004).

DOI: 10.1142/s0218001404003228

[2] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, el al. A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, no. 10, pp.1367-1372,. (2004).

DOI: 10.1109/tpami.2004.75

[3] B.D. McKay, Practical Graph Isomorphism, Congressus Numerantium, vol. 30, pp.45-87, (1981).

[4] E.M. Luks, Isomorphism of Graphs of Bounded Valence can be Tested in Polynomial Time, J. Computer System Science, pp.42-65, (1982).

DOI: 10.1016/0022-0000(82)90009-5

[5] A. Massano, M. Pelillo. A linear Complementary approach to Graph matching. Proc. Of GbR'01, 3rd IAPR TC15 Int. Workshop on Graph based Representation(isbn887146579-2), 160-169(2001).

[6] J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the Association for Computing Machinery, vol. 23, pp.31-42, (1976).

[7] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, Subgraph Transformations for the Inexact Matching of Attributed Relational Graphs, Computing, suppl. 12, pp.43-52, (1998).

DOI: 10.1007/978-3-7091-6487-7_5

[8] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, An Improved Algorithm for Matching Large Graphs, Proc. of the 3rd IAPR-TC-15 International Workshop on Graph-based Representation, Italy, (2001).

[9] LI Feng, LI Xiaoyan, Isomorphism Testing Algorithm for Graphs: Incidence Degree Sequence Method and Applications, Journal of Fundan University (Natural Science), vol. 40, pp.318-325, (2001).

[10] CHEN Ling, YIN Xinchun, Parallel Algorithm for Testing Isomorphism of Undirected Graphs, Computer Engineering, vol. 28, no. 6, (2002).

[11] L.P. Cordella, P. Foggia, C. Sansone, M. Vento, Fast Graph Matching for Detecting CAD Image Components, Proc. of the 15th Int. Conf. on Pattern Recognition, IEEE Computer Society Press, vol. 2, pp.1038-1041, (2000).

DOI: 10.1109/icpr.2000.906251

[12] P. Foggia, C. Sansone, M. Vento, A Database of Graphs for Isomorphism and Sub-Graph Isomorphism Benchmarking, Proceedings of the 3rd IAPR-TC15 Workshop on Graph based Representation (GbR2001), Italy, (2001).

DOI: 10.1016/s0167-8655(02)00253-2