应用数学学报
首页  |  期刊介绍  |  编 委 会  |  投稿指南  |  期刊订阅  |  广告服务  |  相关链接  |  下载中心  |  联系我们  |  留言板
 
应用数学学报 英文版  
   
   
高级检索 »  
应用数学学报  2003, Vol. 26 Issue (3): 408-412    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索  |   
子图识别的层分解方法
徐以汎
复旦大学管理学院,上海200433
RECOGNIZE SUBGRAPHS BY LAYER-DECOMPOSITION
Yi Fan XU
School of Management, Fudan University, Shanghai 200433,P.R.Cina
 全文: PDF (0 KB)   HTML (0 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 子图识别问题(SRP)就是在一个图G中确定并寻找是否存在和另一个图H相同构的子图,本文将引入图的层分解概念,并以此为基础建立识别图的同构子图的算法,该算法的复杂性为O((△-1)~(k-1))其中△为G 的度,即G中点的最大度,n,k分别是图G,H的阶。
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
徐以汎
关键词平面图   支撑树   层分解   子图识别     
Abstract: The subgraph recognition problem (i.e., SRP) is to determine wether there are some subgraphs in a graph G which are isomorphic to a given graph H. In the paper, the layer-decomposition of the graph and the algorithm based on the idea for recognizing isomorphic subgraphs are introduced.The complexity of the algorithm is O((△-1)~(k-1)),where △ is the degree of G,i.e.,the maximum degree of vertices in Gand n,k are the orders of G,H respectively.
Key wordsPlanar graph   spanning tree   subgraph recognition   layer-decomposition   
收稿日期: 1900-01-01;
引用本文:   
徐以汎. 子图识别的层分解方法[J]. 应用数学学报, 2003, 26(3): 408-412.
Yi Fan XU. RECOGNIZE SUBGRAPHS BY LAYER-DECOMPOSITION[J]. Acta Mathematicae Applicatae Sinica, 2003, 26(3): 408-412.
 
没有本文参考文献
[1] 闫晓霞);李建湘(). 推广的奇轮的圆色数[J]. 应用数学学报, 2005, 28(1): 86-99.
[2] 闫晓霞);李建湘(). 推广的奇轮的圆色数[J]. 应用数学学报, 2005, 28(1): 86-99.
[3] 闫晓霞);李建湘(). 推广的奇轮的圆色数[J]. 应用数学学报, 2005, 28(1): 86-99.
[4] 闫晓霞);李建湘(). 推广的奇轮的圆色数[J]. 应用数学学报, 2005, 28(1): 86-99.
[5] 闫晓霞);李建湘(). 推广的奇轮的圆色数[J]. 应用数学学报, 2005, 28(1): 86-99.
[6] 闫晓霞);李建湘(). 推广的奇轮的圆色数[J]. 应用数学学报, 2005, 28(1): 86-99.
[7] 徐以汎. 子图识别的层分解方法[J]. 应用数学学报, 2003, 26(3): 408-412.
[8] 徐以汎. 子图识别的层分解方法[J]. 应用数学学报, 2003, 26(3): 408-412.
[9] 徐以汎. 子图识别的层分解方法[J]. 应用数学学报, 2003, 26(3): 408-412.
[10] 徐以汎. 子图识别的层分解方法[J]. 应用数学学报, 2003, 26(3): 408-412.
[11] 徐以汎. 子图识别的层分解方法[J]. 应用数学学报, 2003, 26(3): 408-412.
[12] 王维凡();张克民(). △-匹配与边面全色数[J]. 应用数学学报, 1999, 22(2): 236-242.
[13] 王维凡();张克民(). △-匹配与边面全色数[J]. 应用数学学报, 1999, 22(2): 236-242.
[14] 王维凡();张克民(). △-匹配与边面全色数[J]. 应用数学学报, 1999, 22(2): 236-242.
[15] 王维凡();张克民(). △-匹配与边面全色数[J]. 应用数学学报, 1999, 22(2): 236-242.
  版权所有 © 2009 应用数学学报编辑部   E-mail: amas@amt.ac.cn
京ICP备05002806号-9