JISE

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Information Science and Engineering, Vol. 15 No. 3, pp. 337-352

A New Graph Invariant for Graph Isomorphism: Probability Propagation Matrix

Gow-Hsing King and Wen-Guey Tzeng
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.

The graph isomorphism problem is to determine whether two given graphs are isomorphic or not. In this paper, we present a new graph invariant, called the probability propagation matrix. By means of this graph invariant, we present a heuristic algorithm for the problem. The algorithm is easy to implement and highly parallelizable.

Keywords: graph isomorphism, graph invariant, probability propagation matrix, parallel computing

Retrieve PDF document (JISE_199903_01.pdf)