No label defined (Q4395331)

The authors study budget constrained optimal network upgrading problems. In the node based upgrading model, we are given a connected graph \(G= (V,E)\). For every \(uv\in E\), we are given three nonnegative numbers: \(d(uv)\), its delay; \(d_m(uv)\), its medium delay; \(d_\ell(uv)\), its low delay. If we upgrade \(u\) or \(v\), the delay of \(uv\) becomes its medium delay; and if we upgrade both \(u\) and \(v\), the delay becomes the low delay. The cost of upgrading a set of nodes equals the sum of costs to upgrade each of them. The aim is to minimize the total delay of a minimum spanning tree after a sequence of node upgradings whose total cost is restricted. The complexity of this and related problems is studied. Known results are reported. For the entire collection see [Zbl 0889.00029].