应数学与统计学院徐守军教授与李宪越副教授邀请，西安交通大学数学与统计学院王卫教授将于2018年06月20日至23日访问我校并作学术报告。
报 告1：Constant Approximation for k-connected m-dominating Set Problem in Unit Disk Graphs
时 间：06月20日下午16:30
地 点：齐云楼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
时 间：06月22日上午09:30
地 点：齐云楼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余篇。主持（完成）国家自然科学基金面上项目两项。
应用数学与复杂系统省级重点实验室
数学与统计学院
萃英学院
2018年06月19日