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

• 作 者: 幸冬梅
• 机 构: 复旦大学计算机科学与工程系,南昌大学数学系
• 出 处: 计算机研究与发展
• 发表日期: 2008年z1期
• 关键词: 图分解 事务调度 v-separable 独立子图 graph decomposition transaction scheduling v-separab
• 基金项目: 国家自然科学基金项目(60496321)

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