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

Journal of Inforamtion Science and Engineering, Vol.15 No.3, pp.337-352 (May 1999)
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

Full Text () Retrieve PDF document (199905_01.pdf : 123,857 bytes)

Received April 1, 1997; accepted October 27, 1997.
Communicated by Wen-Lian Hsu.
* This research was partially supported by the National Science Council, Taiwan, R.O.C., under contract No. NSC 83-0408-E-009-021.