摘要
为了提高有向有环图有向割集生成算法的效率,通过收缩有向有环图环路中的边将有向有环图转换成带收缩顶点的有向无环图,并使得生成有向无环图有向割集的算法可以生成有向有环图的有向割集.在理论上分析了本文提出的算法的时间复杂度和空间复杂度,并进行了实验测试.理论分析和实验测试的结果表明本文提出的算法是很高效的.
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 ...
出处
《玉林师范学院学报》
2009年第5期8-12,共5页
Journal of Yulin Normal University
关键词
有向有环图
有向无环图
割集
directed cycling graph
directed acyclic graph
cutest
