Graph Isomorphism and Identification Matrices: Parallel Algorithms
Graph Isomorphism and Identification Matrices: Parallel Algorithms
复制标题
图同构和辨识矩阵：并行算法
DOI：
10.1109/71.491584
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Lin Chen
中科院分区：
文献类型：
--
作者：
Lin Chen
本文讨论了识别矩阵的一些性质，并展示了识别矩阵在研究图同构问题这一著名的公开问题中的应用。我们表明，给定两个图形的形式，在一定的识别矩阵，同构可以有效地并行测试，如果至少有一个矩阵满足循环1s属性，更有效地并行，如果至少有一个矩阵满足连续1s属性。具有满足连续1s性质的识别矩阵的图包括真区间图和双凸二部图等。这里提出的结果大大拓宽了一类图，有已知的高效的并行同构测试算法。
In this paper, we explore some properties of identification matrices and exhibit some uses of identification matrices in studying the graph isomorphism problem, a famous open problem. We show that, given two graphs in the form of a certain identification matrix, isomorphism can be tested efficiently in parallel if at least one matrix satisfies the circular 1s property, and more efficiently in parallel if at least one matrix satisfies the consecutive 1s property. Graphs which have identification matrices satisfying the consecutive 1s property include, among others, proper interval graphs and doubly convex bipartite graphs. The result presented here substantially broadens the class of graphs for which there are known efficient parallel isomorphism testing algorithms.