| 无向图同构判定的并行算法 |
| |
| 引用本文： | 陈峻,殷新春. 无向图同构判定的并行算法[J]. 计算机工程, 2002, 28(6): 39-40,134 |
| |
| 作者姓名： | 陈峻 殷新春 |
| |
| 作者单位： | 扬州大学工学院计算机系,扬州,225009;南京大学软件新技术国家重点实验室,南京,210093;扬州大学工学院计算机系,扬州,225009;南京大学软件新技术国家重点实验室,南京,210093 |
| |
| 基金项目： | 国家自然科学基金(66074013),国家高性能计算基金(99210),江苏省教育厅自然科学基金(99KJB520003),南京大学软件新技术国家重点实验室开放基金资助项目 |
| |
| 摘 要： | 提出了一种判别无向图同构的方法,该方法根据无向图的邻接矩阵的特征值来判别出图的同构关系,而不需要其它附加信息。同时给出用Jacobi方法求出无向图的邻接矩阵的特征值的一种并行算法,它可以在分布式存储的多处理的多处理机上实现。实验结果表明,此方法是快速有效的,能在较短的运算时间内给出判断结果。
|
| 关 键 词： | 同构 邻接矩阵 特征值 并行算法 |
| 文章编号： | 1000-3428(2002)06-0039-02 |
Parallel Algorithm for Testing Isomorphism of Undirected Graphs |
| |
| CHEN LingYIN Xinchun,. Parallel Algorithm for Testing Isomorphism of Undirected Graphs[J]. Computer Engineering, 2002, 28(6): 39-40,134 |
| |
| Authors: | CHEN LingYIN Xinchun |
| |
| Abstract: | A method for testing isomorphism of undirected graphs is presented. The method tests the isomorphism by computing the ,eigenvalues of the graphs' adjacency matrixes without any further information. To compute the eigenvalues of the adjacency matrixesa parallel algorithm on multiprocessor with distributed memory is also presented. Experimental results show that the method is fast and ,effectiveit can get the test result in a very short time. ;;; |
| |
| Keywords: | IsomorphismAdjacency matrixEigenvalueParallel algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
