Parametric Problems on Graphs of Bounded Tree-width
|
Home About Browse Search Register Subscriptions Deposit Papers Help |
Fernandez-Baca, David and Slutzki, Giora (1992) Parametric Problems on Graphs of Bounded Tree-width. Technical Report TR92-08, Department of Computer Science, Iowa State University.
| Full text available as: | Postscript Adobe PDF |
Abstract
Parametric Problems on Graphs of Bounded Tree-width by David Fernandez-Baca 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 tree-width, 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.
| Subjects: | All uncategorized technical reports |
| ID code: | 00000014 |
| Deposited by: | Staff Account on 22 April 1992 |
Contact site administrator at: ssg@cs.iastate.edu