Topological ordering algorithm for LDAG |
| |
Authors: | GuiPing Wang ShuYu Chen XiaoQin Zhang Zhen Zhou |
| |
Affiliation: | 1. College of Computer Science, Chongqing University, Chongqing 400044, China;2. College of Software Engineering, Chongqing University, Chongqing 400044, China |
| |
Abstract: | Directed Acyclic Graph (DAG) is an important tool for workflow modeling and data provenance management. In these applications, DAG usually performs well. Yet for some workflow applications, except data or control dependencies between atomic tasks, there exists another requirement that each atomic task should be accomplished at an expected stage. Therefore, this paper proposes an improved DAG model – LDAG, in which each vertex has a level. Three cases of the level of vertices are discussed. For a reasonable one of these cases, this paper proposes a topological ordering algorithm and proves its correctness. In addition, it discusses the complexity of the algorithm and some other relevant problems. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|