應(yīng)yl7703永利官網(wǎng)徐守軍教授與李憲越副教授邀請(qǐng)，西安交通大學(xué)yl7703永利官網(wǎng)王衛(wèi)教授將于2018年06月20日至23日訪問(wèn)我校并作學(xué)術(shù)報(bào)告。

報(bào) 告1：Constant Approximation for k-connected m-dominating Set Problem in Unit Disk Graphs
時(shí) 間：06月20日下午16:30
地 點(diǎn)：齊云樓911 報(bào)告廳
摘 要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.

報(bào) 告2：Complexity and Algorithm for the Two Disjoint Connected Dominating Sets Problem on Trees
時(shí) 間：06月22日上午09:30
地 點(diǎn)：齊云樓911 報(bào)告廳
摘 要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.

歡迎廣大師生參加！

報(bào)告人簡(jiǎn)介
王衛(wèi)，西安交通大學(xué)yl7703永利官網(wǎng)教授、博士生導(dǎo)師。1991年在浙江大學(xué)獲學(xué)士學(xué)位，分別于1994年及2006年在西安交通大學(xué)獲碩士及博士學(xué)位。主要研究領(lǐng)域?yàn)榇鷶?shù)圖論與組合最優(yōu)化。在圖譜理論的研究中對(duì)圖的廣義譜刻畫(huà)問(wèn)題做出了一些原創(chuàng)性的工作，給出了圖廣義譜刻畫(huà)的一個(gè)簡(jiǎn)潔的算術(shù)條件，證明了具有廣義譜唯一性的多重圖具有正的密度。在組合優(yōu)化領(lǐng)域中對(duì)一些NP-困難組合優(yōu)化問(wèn)題設(shè)計(jì)出了一些好的近似算法。目前在J. Combin. Theory, Ser B, European J. Combin.以及IEEE/ACM Transactions系列等刊物上發(fā)表研究論文60余篇。主持（完成）國(guó)家自然科學(xué)基金面上項(xiàng)目?jī)身?xiàng)。