scientific article; zbMATH DE number 1163718
Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15) Communication networks in operations research (90B18) Large-scale problems in mathematical programming (90C06)
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].
- Up- and downgrading the 1-center in a network
- Approximation algorithms for certain network improvement problems
- Lagrangian and branch-and-cut approaches for upgrading spanning tree problems
- Improving spanning trees by upgrading nodes
- To improve the communication delay by upgrading nodes in a continuous version
- Improving multicut in directed trees by upgrading nodes
- Optimal upgrading schemes for effective shortest paths in networks
- Best upgrade plans for large road networks
- Robust flows with losses and improvability in evacuation planning
- scientific article; zbMATH DE number 1234975 (Why is no real title available?)
- scientific article; zbMATH DE number 1859293 (Why is no real title available?)
- Network upgrading problems
- Improving Minimum Cost Spanning Trees by Upgrading Nodes
- Upgrading arcs to minimize the maximum travel time in a network
- A GRASP metaheuristic to improve accessibility after a disaster
- Complexity of reducing the delay between two nodes by node-based and edge-based upgrading strategies
- Optimizing cost flows by edge cost and capacity upgrade
- Upgrading \(p\)-median problem on a path
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4395331)
