A Recursive Method for Graph Scheduling

Published in Volume XI, 2002, p. 121-131

Author(s): Claude TADONKI

Abstract

In this paper, we propose a formal method for scheduling regular graphs. The idea is to perform a decomposition of the graph into semi-isomorphic subgraphs, and then recursively propagate a given schedule of the initial subgraph of the chain over the whole graph. The method derives regular schedules, and the class of problems on which it can be applied is less restrictive than what we usually observe. Some complexity results are provided, together with a study on how to use the method as best as possible. The tiling issue is studied in many of its aspects, assuming that the method has been first applied in a fine grain context.