澳门皇冠844网站

澳门皇冠844网站

Notice

【学术校庆】关于西安交通大学王卫教授讲座的通知
发布时间:2018-06-20 浏览次数: 次

报告题目: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日

上一条:关于选聘2018年全国大学生数学建模竞赛引导教师的通知

下一条:2018年中国铁路总企业科技研究开发计划课题申报通知

版权所有  澳门皇冠844网站 通讯地址:兰州市安宁区安宁西路88号 邮编:730070
域名备案信息:[www.vmlsource.com/陇ICP备14001560号-2] [www.lzjtu.cn/陇ICP备14001560号-1]
管理员邮箱:webmaster@lzjtu.edu.cn
甘公网安备 62010002000103号

XML 地图 | Sitemap 地图