报告题目：Complexity and Algorithm for the Two Disjoint Connected Dominating Sets Problem on Trees

报告人：王卫

时 间：2018年6月22日下午16:00

地 点：电信学院大会议室

摘要：

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 cardinality 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年及2002年于西安交通大学获理学硕士及博士学位。主要研究领域为代数图论与组合最优化。在图谱理论的研究中对图的广义谱刻画问题做出了一些原创性的工作，给出了图广义谱刻画的一个简洁的算术条件，证明了具有广义谱唯一性的多重图具有正的密度。在组合优化领域中对一些NP-困难组合优化问题设计出了一些好的近似算法。目前在J. Combin. Theory, Ser B, European J. Combinatorics, 以及IEEE/ACM Transactions系列等刊物上发表研究论文60余篇。主持（完成）国家自然科学基金面上项目两项。

电信学院

2018年6月20日