In this paper, we investigate some properties of identification matrices and exhibit some uses of identification matrices in studying the graph isomorphism problem, a well-known long-standing open problem. We show that, given two m/spl times identification matrices representing two graphs according to a certain relation, isomorphism can be decided efficiently in parallel if an m/spl times/(n-c) submatrix, for a constant c, satisfies the consecutive/circular 1's property. The result presented here significantly broadens the class of graphs for which there are known efficient parallel isomorphism testing algorithms.
展开▼
机译：在本文中，我们研究了识别矩阵的一些性质，并展示了识别矩阵在研究图同构问题（一种众所周知的长期存在的开放问题）中的某些用途。我们表明，给定两个m / spl times / n表示矩阵的两个确定矩阵，按照一定的关系，如果m / spl times /（nc）子矩阵（对于常数c）满足连续，则可以有效地并行确定同构。 / circular 1的属性。此处提供的结果显着拓宽了已知有效并行同构测试算法的图的类别。
展开▼
