混合图在无向图割集生成中的应用  

Application of hybrid graph in cutsets generation of undirected graph

作　　者：梁勇强[1] 朱晓姝[2] 谢妙[2] 

机构地区：[1]玉林师范学院数学与计算机科学系,广西玉林537000 [2]玉林师范学院职业技术学院,广西玉林537000

出　　处：《计算机工程与设计》2010年第11期2648-2653,共6页Computer Engineering and Design

基　　金：广西自然科学青年基金项目(桂科青0832101)

摘　　要：为了进一步提高生成无向图割集的递归收缩算法的执行效率,将无向图转换为一类特殊的混合图,并将转换结果代替无向图输入递归收缩算法进行处理,修改了递归收缩算法中相应的算法步骤,使得改进算法可以更高效地生成无向图的割集。在理论上论证了改进算法的正确性,并通过理论分析和实验比较了改进算法和现有算法的时间复杂度和空间复杂度。理论分析结果和实验比较结果均表明改进算法明显比现有算法高效。In order to further improve the efficiency of recursive contraction algorithm for generating cutsets of undirected graph,undirected graph is converted into a special kind of hybrid graph,and the result of the conversion is processed as the input of recursive contraction algorithm instead of undirected graph,and those related algorithm steps are altered to make the improved algorithm generates the cutsets of undirected graph more efficiently.The correctness of the improved algorithm is proved,and time complexity and space complexity of the improved algorithm and the old one are compared through theoretical analysis and experiments.The results of the theoretical analysis and the experiments show that the improved algorithm is more efficient than the old one.

关 键 词：混合图 无向图 割集 边被收缩图 递归收缩算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]