基于边被收缩图的有向有环图有向割集求解算法  

An Algorithm for Generating Directed Cutsets of Directed Cycling Graph Based on Edge Contracted

作　　者：梁勇强[1] 

机构地区：[1]玉林师范学院数学与计算机科学系

出　　处：《玉林师范学院学报》2009年第5期8-12,共5页Journal of Yulin Normal University

摘　　要：为了提高有向有环图有向割集生成算法的效率,通过收缩有向有环图环路中的边将有向有环图转换成带收缩顶点的有向无环图,并使得生成有向无环图有向割集的算法可以生成有向有环图的有向割集.在理论上分析了本文提出的算法的时间复杂度和空间复杂度,并进行了实验测试.理论分析和实验测试的结果表明本文提出的算法是很高效的.In order to improve the efficiency of the algorithm for generating directed cutsets of directed cycling graph, directed cycling graph is converted to directed acyclic graph with contracted vertices by contracting edge of rings in directed cycling graph, and the algorithm for generating directed cutsets of directed acyclic graph is made to generate directed cutsets of directed cycling graph. Time complexity and space complexity of the proposed algorithm have been analyzed theoretically, and the experimental ...

关 键 词：有向有环图 有向无环图 割集 

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