混合图的同构判定算法:度序列法  

ISOMORPHISM TESTING ALGORITHM FOR MIXED GRAPHS:THE DEGREE SEQUENCE METHOD

作　　者：臧威[1] 李锋[1] 

机构地区：[1]复旦大学电子工程系,上海200433

出　　处：《计算机应用与软件》2008年第3期198-200,共3页Computer Applications and Software

摘　　要：提出了新的混合图的同构判定算法。该算法通过考察图的n点连通子图的度序列对混合图进行同构判定,适合计算机并行处理。实验表明这种方法在多数情况下快捷有效。A new isomorphism-testing algorithm for mixed graphs is proposed. The method determines isomorphism by degree sequences of the n-vertex connected sub-graphs. The algorithm is suitable for parallel implementation on computers. Experiments show that it is efficient and effective in most cases.

关 键 词：混合图 同构判定 度序列 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构] O157.5[自动化与计算机技术—计算机科学与技术]