A new algorithm for isomorphism determination of undirected graphs-circuit simulation method. (English) Zbl 1228.94037
Summary: In this article, an important property of the associated circuits of isomorphic graphs is proved and therefore a criterion for the determination of the isomorphism of two undirected graphs is obtained. With the use of this approach, the isomorphism of two undirected graphs can be determined quickly. The approach proposed is applied to arbitrary connected graphs and irregular 2D meshes for graph isomorphism determination, and satisfactory results are achieved.
MSC:
| 94C15 | Applications of graph theory to circuits and networks |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
References:
| [1] | K. Agusa, S. Fujita, M. Yamashita, T. Ae, On neural networks for graph isomorphism problem, in RNNS/IEEE Symposium on Neuroinformatics and Neurocomputers (Oct 1992), pp. 1142–1148 |
| [2] | C.K. Alexander, Fundamentals of Electric Circuits. McGraw–Hill Science Engineering (2004) |
| [3] | J. Cai et al., The genetic algorithm for graph isomorphism. Proc. SuZhou Sci. Technol. Coll., 23(1), 35–38 (2006) (in Chinese) · Zbl 1111.68611 |
| [4] | L. Chen et al., The parallel algorithm for isomorphism determination of undirected graphs. Comput. Eng. 28(6), 39–40 (2002) (in Chinese) |
| [5] | D. Conte, P. Foggia, C. Sansone, M. Vento, Thirty years of graph matching in pattern recognition. Int. J. Pattern Recognit. Artif. Intell. 18(3), 265–298 (2004) · doi:10.1142/S0218001404003228 |
| [6] | L.P. Cordella, M. Vento, Symbol recognition in documents: a collection of techniques. Int. J. Doc. Anal. Recognit. 3, 73–88 (2000) · doi:10.1007/s100320000036 |
| [7] | P. Foggia, C. Sansone, M. Vento, A database of graphs for isomorphism and sub graph isomorphism benchmarking, in Int’l Workshop on Graph-Based Representations in Pattern Recognition, Italy (2001), pp. 176–188 |
| [8] | P.J.B. Hancock, Genetic algorithms and permutation problems: a comparison of recombination operators for neural network structure specification, in 1992 International Workshop on Combinations of Genetic Algorithms and Neural Networks, Baltimore (1992), pp. 108–122 |
| [9] | F. Harary, Graph Theory (1981) |
| [10] | L. Jianzhuang, L.Y. Tsui, Graph-based method for face identification from a single 2D line drawing. IEEE Trans. Pattern Anal. Mach. Intell. 23(10), 1106–1119 (2001) · doi:10.1109/34.954601 |
| [11] | F. Li, S.-Y. Li, An algorithm for graph isomorphism determination–degree distribution sequence method and its application. J. Fudan Univ. (Nat. Sci.) 40(3), 318–325 (2001) (in Chinese) · Zbl 0985.05049 |
| [12] | F. Li, H.-L. Shang, P.-Y. Woo, Determination of isomorphism and its applications for arbitrary graphs based on circuit simulation. Circuits Syst. Signal Process. 27(5), 749–761 (2008) · Zbl 1173.94472 · doi:10.1007/s00034-008-9054-7 |
| [13] | N. Lloyd et al., Numerical Linear Algebra (SIAM, Philadelphia, 1997) |
| [14] | B.T. Messmer, Efficient graph matching algorithms for preprocessed model graphs. PhD Thesis, Inst. of Computer Science and Applied Mathematics, Univ. of Bern (1996) |
| [15] | M. Pelillo, Replicator equations, maximal cliques, and graph isomorphism. Neural Comput. 11(8), 1933–1955 (1999) · doi:10.1162/089976699300016034 |
| [16] | H.-L. Shang, F. Li, An algorithm for isomorphism determination of undirected graphs: circuit simulation method, in 2009 Annual Meeting of Chinese Professional Committee of Graph Theory and System Optimization, Harbin, China (2009), pp. 56–63 (in Chinese) |
| [17] | P. Stagge, C. Igel, Neural network structures and isomorphism: random walk characteristics of the search space, in IEEE Symposium on Combinations of Evolutionary Computation and Neural Networks (ECNN 2000) (2000), pp. 82–90 |
| [18] | W. Zang, F. Li, The algorithm for isomorphism determination of arbitrary connected graphs: the eigenvector method. Comput. Aided Des. Graphs 19(2), 163–167 (2007) (in Chinese) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
