Scheduling a Pipelined Operator Graph of Bounded Treewidth
Pipelined operator graph (POG) scheduling is an important problem in the area of parallel query optimization. A POG is a graph with vertices representing query operators that can run in parallel and edges representing communication between adjacent operators. The problem is to assign operators to processors so as to minimize the maximum processor load. We present a 2-approximation algorithm for the case where the operator graph has bounded treewidth.
S. G. Li and X. Xin, "Scheduling a Pipelined Operator Graph of Bounded Treewidth", Key Engineering Materials, Vols. 467-469, pp. 1102-1107, 2011