同构图判定:改进的电路模拟法

• 作者: 商慧亮 李锋 赵愉
• 来源期刊: 信息与电子工程
• 学科: 工学
• 关键词: 无向图 同构判定 电路模拟法 算法复杂度
• 年，卷（期）: 2011,（4）
• 所属期刊栏目: 信号与信息处理
• 页码范围: 478-482
• 分类号: TN702
• 字数: 3621字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-2892.2011.04.018

摘要

针对无向图的同构判定,提出一种改进的电路模拟法.该算法在原电路模拟法的基础上,通过添加1个参考节点,从而使原来需求解2n个n-1阶的线性代数方程组变为求解2个n阶的线性方程组(n为图的顶点数).与原有算法相比较,算法复杂度大大降低,对于大规模图的同构判定具有明显的优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李锋	复旦大学电子工程系	92	925	14.0	27.0
2	商慧亮	复旦大学电子工程系	15	137	5.0	11.0
3	赵愉	复旦大学电子工程系	4	18	3.0	4.0