Algorithms for the Generalized Network Construction Problem

This research is motivated by the network construction problem studied in [2], [5], [8]-[10]. It has applications in the areas of overlay network construction and wireless coverage of networks. Given a weighted undirected graph and a list of requests of connectivity constraints on some subsets of vertices, the objective is to form connected subgraphs such that all the connectivity constraints are satisfied and the total cost of the selected edges is minimized. This problem was proved APX-complete [8], [9]. In the past two decades, the network construction problem and its variants have been studied in both online and offline settings. The performance of these variants' algorithms relies on the sizes of the connectivity constraints. In this work, we generalize the problem by introducing Steiner vertices into connectivity constrains. We focus on designing algorithms for this Steiner network construction problem on various graph topologies. We present efficient optimal online and offline algorithms for this problem's variants, particularly, on cycles and bipartite graphs. Our algorithmic approaches are new in dealing with this network construction problem and its variants.