Existing algorithms that solve the Constrained Bottleneck Spanning Tree Problem (CBST) are implemented and converted to solve the CBSTU:
- The Constrained Bottleneck problem in Networks Berman et al.
- An Improved Algorithm for the Constrained Bottleneck Spanning Tree Problem by Punnen & Nair
Problem tailored Edge Elimination algorithm provides fastest performance. Calculating lower and upperbound beforehand is the bottleneck in the Punnen algorithm, so we avoid calculating bounds beforehand and use a binary search combined with updating the working graph (eliminating edges) to increase performance.
If this repository useful for your work, please cite the following publictation:
@article{coulier2024constrained,
title={The constrained Bottleneck Spanning Tree Problem with upgrades},
author={Coulier, Bryan and {\c{C}}al{\i}k, Hatice and Vanden Berghe, Greet},
journal={Discrete Applied Mathematics},
volume={353},
pages={12--28},
year={2024},
publisher={Elsevier}
}