

FernandezBaca, David and Slutzki, Giora (1992) Parametric Problems on Graphs of Bounded Treewidth. Technical Report TR9208, Department of Computer Science, Iowa State University.
Abstract
Parametric Problems on Graphs of Bounded Treewidth
by
David FernandezBaca and Giora Slutzki
We consider optimization problems on weighted graphs where vertex and
edge weights are polynomial functions of a parameter lambda. We show
that, if a problem satisfies certain regularity properties and the
underlying graph has bounded treewidth, the number of changes in the
optimum solution is polynomially bounded. We also show that the
description of the sequence of optimum solutions can be constructed in
polynomial 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.
Contact site administrator at: ssg@cs.iastate.edu
