无线传感网络及社交网络中几类控制集问题的近似算法

Dominating set problem is a classic problem in graph theory and combinatorics, which has attracted a lot of attentions of researchers including K.F. Gauss. In recent years, with the rapid developments of computer science and communications, various dominating set problems have found more and more applications in real domains. For example, in wireless sensor networks, virtual backbone, which has proved to play an important role in efficient routing, can be modeled by connected dominating set; in social networks, information (rumors) propagation can be modeled successfully by some variants of dominating set. Motivated by these applications, the project will focus on three variants of dominating set problem: Minimum Partial Connected Dominating Set Problem in United Disk Graph, Disjoint Connected Dominating Set Problem and t-Latency Bounded Target Set Selection Problem. We will analyze the complexity and design algorithms for these problems, especially the design and analysis of approximation algorithms. Therefore, the research of our project will play an important role in enriching the contents of dominating set theory. One the one hand, these problems have important applications in the real world; on the other hand, we will develop new techniques of designing approximation algorithms through the study of these problem and then apply these new methods to more problems. The project is very challenging and our previous work has laid the foundation for this project.

控制集问题是图论与组合数学中的一个经典问题，吸引了包括高斯在内的许多数学家的广泛研究。近年来，随着计算机、通讯等领域的迅猛发展，控制集及其各类形变问题在诸多实际领域中得到了广泛的应用(譬如在无线传感网络的网络路由中，虚拟骨干网可以很好地由连通控制集来模拟；在社交网络中，信息或谣言的传播可以很好的用一类形变的控制集来模拟)。基于以上应用的驱动，本项目将致力于研究三类形变的控制集问题：单位圆盘图上的最小偏连通控制集问题、不相交连通控制集问题以及带时滞的目标集选择问题。我们将研究以上三类问题的复杂性分析和算法的设计，特别是近似算法的设计与分析。一方面这些问题的研究有着重要的实际背景和意义，另一方面通过对这些问题的研究我们拟致力于发展新的近似算法的设计方法与技巧，从而应用到更多的实际问题中去。尽管本项目的研究具有很大的挑战性，但我们前期的研究为项目的开展打下了坚实的基础。

控制集问题是图论与组合数学中一个重要且困难的问题。由于近些年控制集的形变问题能很好地模拟无线传感网络的虚拟骨干网和社交网络中的信息或谣言的传播机制，所以得到了研究人员的广泛关注。本项目按计划对无线传感网络和社交网络中应用极为广泛的三类形变控制集问题，即最小偏连通控制集问题、不相交连通控制集问题和带时滞的目标集选择问题，进行了深入研究。本项目取得的主要研究成果如下：对最小偏连通控制集问题取得了宝贵的研究经验。在树上得到了不相交连通控制集问题的两个紧的下界。证明了不相交连通控制集问题在树上是一个NP-hard问题。在树上设计了一个近似比为3/2+O(1/n)的近似算法。给出了任意一个3-正则图为一个不相交连通控制集图的必要条件，并证明了该必要条件不是充分条件。给出并证明了任意一个不相交连通控制集图的girth的上界。在一些特殊图上，诸如grid graphs、cylinder mesh graphs、toroidal mesh graphs以及由圈产生的tensor products，给出了不相交连通控制集问题的最优解。对带时滞的目标集选择问题，提出了一个更符合实际应用的新模型，即带时滞的强目标集选择问题。在任一图上，给出并证明了带时滞的强目标集中顶点的度之和的一个紧的下界。利用这个紧的下界，给出并证明了一个顶点子集是一个最小带时滞的强目标集的充分必要条件。利用该充分必要条件，在一些特殊图类上，即Toroidal Meshs、高维的Toroidal Meshs、Tensor Products，找到了带时滞的强目标集选择问题的最优解，并给予了证明。