基于图的分解与合并的静态事务调度算法

摘要：

在各种数据系统的处理中,总有一系列相对独立而相互关联的事务系列组成.如何合理地安排这样的事务的顺序,一直是数据系统优化中存在的问题.该问题的一般化形式是一个NP问题,可以归约为一个点、边均有权值的图上有多输入、多输出问题,寻找时间代价最小且使得点和边尽可能满足容量需求的最短路径.为此,考虑一种基于图的分解与合并的计算方法,利用一种新的算法,并从理论上分析其优良性.

关键词： 图分解 事务调度 v-separable 独立子图 最短路径

作者: 幸冬梅

作者单位: 复旦大学计算机科学与工程系,上海,200433;南昌大学数学系,南昌,330047

会议类型: 国内会议

会议名称: 2007全国理论计算机科学学术年会

会议地点: 南宁

会议语种:中文

页码: 57-61

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