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 + n log n) 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) · log n) and O(m + gk(n) · log n) 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 the k-edge-connectivity requirement and for k ≥ 3 in the case of k-node-connectivity requirement.