PARAMETRIC PROBLEMS ON GRAPHS OF BOUNDED TREE-WIDTH

We consider optimization problems on weighted graphs where vertex and edge weights are polynomial functions of a parameter lambda. We show t hat, if a problem satisfies certain regularity properties and the unde rlying graph was bounded tree-width, the number of changes in the opti mum solution is polynomially bounded. We also show that the descriptio n of the sequence of optimum solutions can be constructed in polynomia l time and that certain parametric search problems can be solved in O( n log n) time, where n is the number of vertices in the graph. (C) 199 4 Academic Press, Inc.