摘要
为了进一步提高生成无向图割集的递归收缩算法的执行效率,将无向图转换为一类特殊的混合图,并将转换结果代替无向图输入递归收缩算法进行处理,修改了递归收缩算法中相应的算法步骤,使得改进算法可以更高效地生成无向图的割集。在理论上论证了改进算法的正确性,并通过理论分析和实验比较了改进算法和现有算法的时间复杂度和空间复杂度。理论分析结果和实验比较结果均表明改进算法明显比现有算法高效。
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.
出处
《计算机工程与设计》
CSCD
北大核心
2010年第11期2648-2653,共6页
Computer Engineering and Design
基金
广西自然科学青年基金项目(桂科青0832101)
关键词
混合图
无向图
割集
边被收缩图
递归收缩算法
hybrid graph
undirected graph
cutest
edge-contracted graph
recursive contraction algorithm
