archives

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