کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
483300 | 1446213 | 2006 | 13 صفحه PDF | دانلود رایگان |
In this paper, we consider a class of node based bottleneck improvement problems with respect to the system (V,E,F)(V,E,F), where V is a node set, E is an edge set, and F⊆2EF⊆2E is a nonempty family of subsets of E. In the node based upgrading model, a node v can be upgraded at the expense of c(v), and such an upgrade reduces weights on all edges incident to v. For a given budget B, the objective is to upgrade a subset of nodes S ⊆ V such that the bottleneck weight of the family FF is minimum under the constraint that the overall upgrade cost c(S) does not exceed B . The problem includes some NP-hard cases. For the special tree-path system (V,E,F)(V,E,F), in which T = (V, E ) is a rooted tree and FF is a set of paths from the root to the leaves, we present an O(n log n) algorithm, where n = ∣V∣. We also consider some variations of this problem. Some related complexity results and algorithms are also presented.
Journal: European Journal of Operational Research - Volume 174, Issue 3, 1 November 2006, Pages 1540–1552