講座名稱：Localization in Graphs and Sequential Metric Dimension

講座時(shí)間：2019-09-04 10:00:00

講座地點(diǎn)：南校區(qū)信遠(yuǎn)樓二區(qū)206室

講座人：Nicolas NISSE

講座人介紹：

自2019年起Nicolas NISSE是法國(guó)信息與自動(dòng)化研究所COATI項(xiàng)目組的全職研究員，曾就讀在巴黎第十一大學(xué)研究院并于2007年獲得計(jì)算機(jī)科學(xué)專業(yè)博士學(xué)位且于2004年獲得信息專業(yè)碩士。分別于2008-2009和2007-2008在法國(guó)信息與自動(dòng)化研究所和智利大學(xué)做博士后，于2014年獲得尼斯大學(xué)Habilitation Diriger des Recherches。

他的主要研究方向包括圖論，算法與組合優(yōu)化，致力于研究圖論中的組合游戲 (圖搜索，警察與小偷等)，同時(shí)研究信息網(wǎng)絡(luò)中的信息傳播問題(如，路由算法)。他是利用圖結(jié)構(gòu)（如，樹分解）和網(wǎng)絡(luò)距離特征設(shè)計(jì)算法的專家，已發(fā)表四十余篇期刊論文 (如，Algorithmica, SIAM j. of Discrete Maths, Distributed Computing, TCS, DAM, etc.)及三十余篇會(huì)議論文 (ICALP, ESA, STACS, WG, DISC, PODC...)，已多次承擔(dān)會(huì)議學(xué)術(shù)委員會(huì)及組織委員(如，CIAC19,SEA18,FCT17,AdHoc-Now15, LAGOS15, AlgoTel)，已指導(dǎo)三名博士研究生和十五名碩士研究生或本科畢業(yè)生，主持或參與的項(xiàng)目包括European project FP7 EULER, COST 295 DYNAMO, Anillo en Redes, ANR AGAPE, ANR DIMAGREEN, ANR STINT等，在世界各地都有合作者，包括加拿大，巴西，智利，希臘，意大利，日本，挪威，中國(guó)等，與公司如 Alcatel-Lucent和 Amadeus，也有合作項(xiàng)目。

講座內(nèi)容：

We present our work on different variants of the metric dimension of graphs.

Given a graph G we want to localize a walking agent by checking his (exact or relative) distance to as few vertices as possible. The model we introduce is based on a pursuit graph game that resembles the famous Cops and Robbers game. It can be considered as a game theoretic variant of the metric dimension of a graph. We provide upper bounds on the related graph invariants, defined as the least number of cops needed to localize the robber on a graph G, for several classes of graphs (trees, bipartite graphs, outerplanar graphs, treewidth-2 graphs, etc).

In the case when the target is not moving, one cop is always sufficient to localize it. In that case, we study the tradeoff between the number of cops and the number steps that are needed to localize the target.

Finally, we study the metric dimension of oriented graphs.

主辦單位：數(shù)學(xué)與統(tǒng)計(jì)學(xué)院