有向图的完全调度

摘要：

为了从有向图的一般性的结构信息中获取有问图中结点和边的控制顺序，本文提出了有向图的完全调度问题。如果这个问题只是针对简单有向无环图，那么一个简单的拓扑排序算法就可以解决问题。但是如果有向图中的边构成了环，简单的拓扑排序算法就无法消解图中的环，这时需要对环进行等价分解。文中提出了调度的概念并给出了等价分解的几个定理，最后得到了获得有向图的完全调度的算法。

关键词： 有向图 完全调度 广义拓扑排序 等价分解

作者: 王黎亮 刘循 王勇 赵国庆 严江浩

作者单位: 四川大学计算机学院 成都 610064 中国人寿四川分公司信息技术部 成都 610064

会议类型: 国内会议

会议名称: 2008年中国信息技术与应用学术论坛

会议地点: 成都

会议语种:中文

页码: 385-387,393

在线出版日期: 2008-04-01（万方平台首次上网日期，不代表论文的发表时间）