ECCO 2024
Abstract Submission

44. The constrained bottleneck spanning tree problem with upgrades

Invited abstract in session FB-1: Complexity, stream Complexity.

Friday, 10:30 - 12:00
Room: L226

Authors (first author is the speaker)

1. Bryan Coulier
Computer Science, KU Leuven
2. Hatice Calik
Department of Electrical Engineering, KU Leuven
3. Greet Vanden Berghe
Computer Science, KU Leuven

Abstract

Upgrading the connections of an existing network is common in the context of telecommunication and electric grid networks. Constructing a new network from scratch is typically not a viable option due to resource constraints, especially for low-voltage grids. Moreover, if the underlying network structure necessitates a tree configuration, this results in a novel variant of the Constrained Bottleneck Spanning Tree Problem (CBST), which is referred to as the Constrained Bottleneck Spanning Tree Problem with Upgrades (CBSTU). This novel variant considers potential edge upgrades with a corresponding cost for each upgrade. There are only two existing polynomial-time algorithms that can tackle this problem after transforming the network into a CBST instance in linear time. Furthermore, a computational study highlights the strengths and weaknesses of these algorithms. By combining the strengths of these existing algorithms, a novel polynomial-time Edge Elimination (EE) algorithm is proposed. The EE algorithm builds on the strengths of both existing algorithms by combining progressive network reduction and binary search. Specifically, the EE algorithm identifies a subset of edges to remove during each iteration, thereby simplifying the network and reducing the overall complexity of the problem. Furthermore, the algorithm utilizes binary search in order to efficiently reach an optimal solution. Our new algorithm outperforms both previous algorithms in terms of computation speed and lays the foundation for future research into the CBSTU.

Keywords

Status: accepted

Back to the list of papers