Bottleneck Steiner subnetwork problems with k-connectivity constraints

The objective is to connect a given set of terminal nodes of a network by a subnetwork of maximum bottleneck capacity. The bottleneck capacity of a subnetwork is the minimum of the capacities of its edges. For the problem with the additional requirement that the connecting subnetwork must be k-edge-connected or k-node-connected, k=2,3, algorithms with complexities O(m+nlogn) are given, where m and n are the numbers of edges and nodes of the network respectively. For the problem where the connecting subnetwork is required to be k-edge-connected or k-node-connected, k≥4, the complexities of the proposed algorithms are O(m+fk(n)ëlogn) and O(m+gk(n)ëlogn) respectively, where fk(m)(gk(m)) is the complexity of finding nontrivial k-edge-connected components (k-node-connected components) of a network. The results of the paper improve known complexities for k≥2 in the case of k-edge-connectivity requirement and for k≥3 in the case of k-node-connectivity requirement.