Optimal Parametric Search on Graphs of Bounded Tree-Width
Date
1994-10-13
Authors
Fernández-Baca, David
Slutzki, Giora
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
Abstract
We give linear-time algorithms for a class of parametric search problems on weighted graphs of bounded tree-width. We also discuss the implications of our results to approximate parametric search on planar graphs.