Coverage and connectivity: Algorithm, analysis and application

The coverage and connectivity problems are the most fundamental but essential category of problems we need to deal with in various networks. They involve all kinds of aspects of networks, varying from the management of networks, such as the monitoring of the sensor networks, to the application of networks, such as the application of viral marketing in the social networks. Abstracting various networks as graphs, the coverage problems concern how to select a subset of nodes from the graphs so that the rest of the nodes are covered. And the connectivity problems concern how to connect a given set of nodes in the graphs together so that the cost is minimized.In this dissertation, considering the importance of the coverage and connectivity problems in various networks, we first study the algorithm design and analysis of several optimization problems that are highly related. The specific optimization problems related to the coverage problems that we study are the Minimum Connected Dominating Set problem in the 3-dimensional space, modeled by unit ball graphs, and the Minimum-Weighted Dominating Set problem in the 2-dimensional space, modeled by unit disk graphs. Utilizing the optimization strategies, we propose our own approximation algorithms for these problems. Systematic theoretical analysis and studies show that both of our algorithms outperform the existing work in the literature and are considered the best results up till now. The specific optimization problems related to the connectivity problems that we study are the Selected-Internal Steiner Minimum Tree and the Node-Weighted Steiner Minimum Tree. We proposed a (1+epsilon)-approximation algorithm for selected-internal Steiner minimum tree problem based on the best known result of the Steiner minimum tree. We also propose the first constant approximation algorithm and a Polynomial Time Approximation Scheme (PTAS) for the node-weighted Steiner tree on unit disk graphs as well.Afterwards, we study several coverage and connectivity problems arisen from real scenarios in various networks as applications. The first coverage and connectivity problem we study about is the virtual backbone construction in the wireless networks. We provide both theoretical and experimental studies for the construction of a virtual backbone in the wireless networks considering three essential factors (size, diameter and fault tolerance) together. To our knowledge, it is the first work to study these three factors in a single model in the literature. The contributions of this work are twofold. First, in our study, we testify our claim on the existence of tradeoffs between these three factors using both theoretical analysis and simulations. Results prove the correctness of our claim. Secondly, we provide an approximation algorithm with both low time and space complexity for this problem and the performance is adjustable by user defined input. Another application of the coverage and connectivity problem we study about is from social networks, which have attracted a massive attention in the recent years. Motivated by its wide applications in marketing and the importance of bounding the latency of information spreading in it, we propose a new problem called Fast Information Propagation problem. We first study the hardness of this problem and then we propose a performance-bounded approximation algorithm to address it. Extensive experiments are conducted on a large collaboration network to verify that our algorithm outperforms the node-selection heuristics, which utilizes the well-known approaches based on the node centrality in the social network analysis.