| 基于边被收缩图的有向有环图有向割集求解算法 |
| |
| 引用本文： | 梁勇强.基于边被收缩图的有向有环图有向割集求解算法[J].玉林师范学院学报,2009,30(5). |
| |
| 作者姓名： | 梁勇强 |
| |
| 作者单位： | 玉林师范学院,数学与计算机科学系,广西,玉林,537000 |
| |
| 摘 要： | 为了提高有向有环图有向割集生成算法的效率,通过收缩有向有环图环路中的边将有向有环图转换成带收缩顶点的有向无环图,并使得生成有向无环图有向割集的算法可以生成有向有环图的有向割集.在理论上分析了本文提出的算法的时间复杂度和空间复杂度,并进行了实验测试.理论分析和实验测试的结果表明本文提出的算法是很高效的.
|
| 关 键 词： | 有向有环图 有向无环图 割集 |
An Algorithm for Generating Directed Cutsets of Directed Cycling Graph Based on Edge Contracted |
| |
| LIANG Yong-qiang.An Algorithm for Generating Directed Cutsets of Directed Cycling Graph Based on Edge Contracted[J].Journal of Yulin Teachers College,2009,30(5). |
| |
| Authors: | LIANG Yong-qiang |
| |
| Institution: | LIANG Yong-qiang (Associate Professor; Department of Mathematics and Computer Science; Yulin Normal University; Yulin; Guangxi 537000); |
| |
| Abstract: | 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 ... |
| |
| Keywords: | directed cycling graph directed acyclic graph cutest |
| 本文献已被 维普 万方数据 等数据库收录！ |
