Localization in Graphs and Sequential Metric Dimension

讲座名称：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.

主办单位：数学与统计学院