| 无向图同构的快速算法 |
| |
| 引用本文： | 侯爱民,郝志峰,胡传福,陆海鹏. 无向图同构的快速算法[J]. 华南理工大学学报(自然科学版), 2011, 0(10): 79-83 |
| |
| 作者姓名： | 侯爱民 郝志峰 胡传福 陆海鹏 |
| |
| 作者单位： | 华南理工大学计算机科学与工程学院; |
| |
| 基金项目： | 国家自然科学基金资助项目(61070033); 广东省自然科学基金重点项目(9251009001000005); 广东省科技计划项目(2010B050400011,2010B080701070) |
| |
| 摘 要： | 规范标记算法和顶点划分算法是判断无向图同构的两种重要途径,其缺点是要么无法对图进行规范标记,从而不能进行判断;要么必须进行不断地回溯和试探,从而造成指数阶时间开销.对于任何两个同构的无向图,各自新增一个顶点和若干条关联边,可获得父图.当且仅当新增顶点的邻接点在原同构图中保持同构关系时,父图同构.根据这个充要条件,文中使...
|
| 关 键 词： | 子图同构 快速算法 规范标记算法 顶点划分算法 |
Fast Algorithm for Undirected Graph Isomorphism |
| |
| Hou Ai-min Hao Zhi-feng Hu Chuan-fu Lu Hai-peng. Fast Algorithm for Undirected Graph Isomorphism[J]. Journal of South China University of Technology(Natural Science Edition), 2011, 0(10): 79-83 |
| |
| Authors: | Hou Ai-min Hao Zhi-feng Hu Chuan-fu Lu Hai-peng |
| |
| Affiliation: | Hou Ai-min Hao Zhi-feng Hu Chuan-fu Lu Hai-peng(School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China) |
| |
| Abstract: | The two important methods of distinguishing undirected graph isomorphism,namely the canonical labeling algorithm and the vertex partition algorithm,both have their own disadvantages.Specifically,the former can not work for those graphs which cannot be canonically labeled,and,this latter has to backtrack and try again and again,which results in exponential time cost.For any two isomorphic undirected graphs,new supergraphs can be constructed by adding a new vertex and its incident edges to each graph.The supe... |
| |
| Keywords: | undirected graph isomorphism fast algorithm canonical labeling algorithm vertex partition algorithm |
| 本文献已被 CNKI 等数据库收录！ |
|
