The constrained Bottleneck Spanning Tree Problem with upgrades.

Upgrading the connections of an existing network is common practice in telecommunication and electric grid networks. In most applications such as low-voltage grids, upgrading is preferable compared to building a new network from scratch given the limited resources available. When the structure of the underlying network is required to be a tree, this leads to a novel variant of the Constrained Bottleneck Spanning Tree Problem (CBST) that takes into account edge weight variability. There are only two existing polynomial-time algorithms that can tackle this problem after transforming the network into a CBST instance in linear time. Through a computational study, we highlight the strengths and weaknesses of these approaches. By combining the strengths of these algorithms, namely progressive network reduction and iterative bound alteration, we developed a polynomial-time algorithm that outperforms both existing algorithms in terms of computation speed. Beyond solving the practical problem at hand, this paper lays the foundations for future research into what we term the Constrained Bottleneck Spanning Tree Problem with Upgrades (CBSTU). [ABSTRACT FROM AUTHOR]