PARAMETRIC MODULE ALLOCATION ON PARTIAL KAPPA-TREES

We study the problem of allocating modules to processors in a distribu ted system to minimize total costs when the underlying communication g raph is a partial k-tree and all costs are linear functions of a real parameter t. We show that if the number of processors is fixed, the se quence of optimum assignments that are obtained as t varies from zero to infinity can be constructed in polynomial time. As an auxiliary res ult, we develop a linear time separator algorithm for k-trees. We disc uss the implications of our results for parametric versions of the wei ghted vertex cover, independent set, and 0-1 quadratic programming pro blems on partial k-trees.