OPTIMAL PARAMETRIC SEARCH ON GRAPHS OF BOUNDED TREE-WIDTH

Authors
FERNANDEZBACA D SLUTZKI G
Citation
D. Fernandezbaca et G. Slutzki, OPTIMAL PARAMETRIC SEARCH ON GRAPHS OF BOUNDED TREE-WIDTH, Journal of algorithms, 22(2), 1997, pp. 212-240
Citations number
37
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
22
Issue
2
Year of publication
1997
Pages
212 - 240
Database
ISI
SICI code
0196-6774(1997)22:2<212:OPSOGO>2.0.ZU;2-U
Abstract
We give linear-time algorithms for a class of parametric search proble ms on weighted graphs of bounded tree-width. We also discuss the impli cations of our results to approximate parametric search on planar grap hs. (C) 1997 Academic Press.