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

A New Graph Invariant for Graph Isomorphism:

Probability Propagation Matrix

**Gow-Hsing King and Wen-Guey Tzeng**

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 (**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.