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

講座時間：2019-09-04 10:00:00

講座地點：南校區信遠樓二區206室

講座人：Nicolas NISSE

講座人介紹：

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

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

講座內容：

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.

主辦單位：數學與統計學院