报 告1：Constant Approximation for k-connected m-dominating Set Problem in Unit Disk Graphs
地 点：齐云楼911 报告厅
摘要1：A dominating set (DS) D of a graph G=(V,E) is a subset of V such that every vertex is either in D or adjacent to a vertex in D. A subset D is a connected dominating set (CDS) if D is a DS and the induced subgraph G[D] is connected. CDS-based routing is an important topic in wireless sensor networks. However, a CDS is usually fragile which easily suffers from the failure of a CDS node. To overcome this shortcut, the fault tolerant CDS was proposed in the literature, which can be modeled as a k-connected m-dominating set ((k,m)-CDS). In the minimum (k,m)-CDS problem, we are given a k-connected unit disk graph representing the wireless sensor network, and are required to find a (k,m)-CDS with minimum cardinality. The problem is unfortunately NP-hard and no constant approximation algorithms are known until recently. In this talk, we shall overview this topic and present a simple constant approximation algorithm for (k,m)-CDS problem in unit disk graphs, for any m>=k>=1.
报 告2：Complexity and Algorithm for the Two Disjoint Connected Dominating Sets Problem on Trees
地 点：齐云楼911 报告厅
摘要2：In the two disjoint connected dominating set problem (DCDS), we are given a graph G=(V,E), and required to find an edge set E' with minimum carnality in its complementary graph such that the new graph G'=(V,EUE') has a pair of disjoint connected dominating set. The DCDS problem is NP-hard even restricted to trees. In this talk, we shall give an NP hardness proof, as well as an approximation algorithm with performance ratio 3/2 asymptotically, for the DCDS problem on trees.
王卫，西安交通大学数学与统计学院教授、博士生导师。1991年在浙江大学获学士学位，分别于1994年及2006年在西安交通大学获硕士及博士学位。主要研究领域为代数图论与组合最优化。在图谱理论的研究中对图的广义谱刻画问题做出了一些原创性的工作，给出了图广义谱刻画的一个简洁的算术条件，证明了具有广义谱唯一性的多重图具有正的密度。在组合优化领域中对一些NP-困难组合优化问题设计出了一些好的近似算法。目前在J. Combin. Theory, Ser B, European J. Combin.以及IEEE/ACM Transactions系列等刊物上发表研究论文60余篇。主持（完成）国家自然科学基金面上项目两项。