A class of node based bottleneck improvement problems ?
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?2E F ? 2 E 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 F F 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 F F is a set of paths from the root to the leaves, we present an O(nlogn) algorithm, where n=?V?. We also consider some variations of this problem. Some related complexity results and algorithms are also presented.
bottleneck improvement problem node based upgrading model np-hard dynamic programming pareto optimality