| 同构图判定：改进的电路模拟法 |
| |
| 引用本文： | 赵 愉,李 锋,商慧亮.同构图判定：改进的电路模拟法[J].太赫兹科学与电子信息学报,2011,9(4):478-482. |
| |
| 作者姓名： | 赵 愉 李 锋 商慧亮 |
| |
| 作者单位： | 复旦大学电子工程系; |
| |
| 摘 要： | 针对无向图的同构判定,提出一种改进的电路模拟法。该算法在原电路模拟法的基础上,通过添加1个参考节点,从而使原来需求解2n个n-1阶的线性代数方程组变为求解2个n阶的线性方程组(n为图的顶点数)。与原有算法相比较,算法复杂度大大降低,对于大规模图的同构判定具有明显的优势。
|
| 关 键 词： | 无向图 同构判定 电路模拟法 算法复杂度 |
| 收稿时间： | 2010/8/13 0:00:00 |
| 修稿时间： | 2010/10/21 0:00:00 |
Improved circuit simulation method for testing isomorphism |
| |
| ZHAO Yu,LI Feng and SHANG Hui-liang.Improved circuit simulation method for testing isomorphism[J].Journal of Terahertz Science and Electronic Information Technology,2011,9(4):478-482. |
| |
| Authors: | ZHAO Yu LI Feng and SHANG Hui-liang |
| |
| Affiliation: | ZHAO Yu,LI Feng,SHANG Hui-liang(Department of Electronic Engineering,Fudan University,Shanghai 200433,China) |
| |
| Abstract: | The problem of determining isomorphism of non-directional graph is solved through the method of circuit.Based on the circuit simulation method,a new method is proposed.It is realized by adding an extra node,so that solving 2n linear system of equations of order n-1 transforms into solving 2 linear systems of equations of order n.Compared with the existent approach,the complexity of the proposed algorithm in this paper is much lower,and this will be an advantage in determining isomorphism of the large graphs... |
| |
| Keywords: | non-directional graph isomorphism circuit simulation method algorithm complexity |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《太赫兹科学与电子信息学报》浏览原始摘要信息 |
|
点击此处可从《太赫兹科学与电子信息学报》下载全文 |
|
