Bottleneck Steiner Subnetwork Problems withk-Connectivity Constraints
INFORMS Journal on Computing · 1996 · Volume 8 · Issue 4
Abstract
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 + f k ( n ) · log n ) and O ( m + g k ( n ) · log n ) respectively, where f k ( m )( g k ( 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.
Keywords
steiner subnetwork, k-connectivity, complexity, efficient algorithms
Enable JavaScript for citation tools and additional paper interactions.