An Algorithm for Testing Isomorphism of Planer Graph Based on Distant Matrix

Abstract:

The testing for graph isomorphism is one of the many problems in the subject of graph theory. This thesis proposes an algorithm for testing isomorphism of planer graph of polynomial time via structuring characteristics of planer graph based on distance matrix. The algorithm, with a time complexity of O (n^4) and a space complexity of O (n^2), has a great application value.

• Periodical: Advanced Materials Research (Volume 487)
• Pages: 317-321
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.487.317
• Online since: March 2012
• Authors: Yan Peng Wu, Shui Qiang Liu
• Keywords: Distance Matrix, Graph Isomorphism, Planer Graph

References

[1] Lindell S. A logspace algorithm for tree canonization. s In: Proceedings of the 24th Annual ACM symposium on theory of computing. 1992. 400~404.

DOI: 10.1145/129712.129750

[2] Chachra V., Ghare V.P. Applications of graph theory algorithms. Elsevier: North Holland, (1979).

[3] LI Feng , LI Xiao yan. Isomorphism Testing Algorithm for Graphs: Incidence Degree Sequence Method and Applications. Journal of Fudan University , 2001, 40(3): 318~325.

[4] Cole R., Crochemore M., Galil Z., et al. Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science(FOCS). 1993. 248~258.

DOI: 10.1109/sfcs.1993.366862

[5] Sen Gupta S., Sinha B.P. A simple O(log n)time parallel algorithm for testing isomorphism of maximal outer planar graphs. Parallel Distrib. Comput., 1999, 144~155.

DOI: 10.1006/jpdc.1998.1514

[6] Buss S.R. A logtime algorithm for tree isomorphism, comparison and canonization. In: Proceedings of the 5th Kurt Codel Colloquium on Computational Logic and Proof Theory. 1997. 18~33.

DOI: 10.1007/3-540-63385-5_30

[7] Grossi R. A note on the subtree isomorphism for ordered tree and related problems. Information and processing letters, 1991, 49(2): 81~84.

DOI: 10.1016/0020-0190(91)90159-f

[8] Yuan-Kai Wang, Kuo-Chin Fan, Jorng-Tzong Horng, Genetic-based search for error-correcting graph isomorphism. IEEE Transactions on Systems, 1997, 27(4): 588~597.

DOI: 10.1109/3477.604100

[9] Riaz K., Khiyal M.S.H., Arshad M. An improved algorithm to discover graph isomorphism. In: Proceedings of INMIC 2003, 7th international Multi Topic Conference 8-9. 2003. 396~399.

DOI: 10.1109/inmic.2003.1416758

[10] Kennedy M.P., Chun L.O. Neural computation of decisions in optimization problems. IEEE Trans. on CAS, 1988, 554~562.

[11] Ae T., Agusa K., Fujita S., et al. On neural networks for graph isomorphism problem. The RNNS/IEEE Symposium on Neuroinformatics and Neurocomputers, 1992, 1142~1148.

DOI: 10.1109/rnns.1992.268621

[12] Onoska N., Karl S.A., Saito M. Three dimensional DNA structures in computing. In: Preceeding of the 4th DNA Based Computing Workshop. Philadephia: Springer Verlag, 1998. 15~19.

[13] Liu Guangwu, Yin Zhixiang, Xu Jin. Algorithm of graph isomorphism with three dimensional DNA graph structures Progress in natural science, 2005, 15(2): 181~184.

DOI: 10.1080/10020070512331341960

[14] OU Fu-un1un, LIU Ping , TU Ya-ping , WU Hai-bing. Improvement and Realization of the Shortest Path Algorithm on the Large-scale Networks, Nature Scieince, outly of Hainan University, 2008 (26),: 183~186.