报告题目：Tree-decomposition with metric properties on the bags
    报告人：Nicolas NISSE 研究员 法国信息与自动化研究所(Inria Sophia Antipolis)
    邀请人：李碧

报告时间：2018年9月5日10:00
    报告地点：信远楼II206数统院报告厅
    报告人简介：Nicolas NISSE (http://www-sop.inria.fr/members/Nicolas.Nisse/) is a full-time researcher at Inria Sophia Antipolis since 2009, in the project-team COATI. He received his engineer diploma from Suplec, in 2004, his Master (2004) and Ph.D. (2007) degrees from LRI, Univ. Paris-Sud 11, and his Habilitation Diriger des Recherches (2014) from Univ. Nice Sophia Antipolis. He did a postdoc at Universidad de Chile (2007-08) and at INRIA (2008-09).
His research interests include graph theory, algorithms and combinatorial optimization. His work mainly focuses on combinatorial games in graphs (graph searching, cops and robber, etc.). He also works on information spreading problems in telecommunication networks (e.g. routing). His expertise concerns the design of algorithms using structural properties (e.g., graph decompositions) and metric properties of networks.
He is co-author of 40 articles in international revues (Algorithmica, SIAM j. of Discrete Maths, Distributed Computing, TCS, DAM, etc.) and more than 35 articles in peer reviewed international conference proceeding (ICALP, ESA, STACS, WG, DISC, PODC...).
He has participated to the Program Committees and Organiation Committees of several international and national conferences (CIAC19,SEA18,FCT17,AdHoc-Now15, LAGOS15, AlgoTel). He supervised 3 Ph.D. students and more than 15 undergraduate/master students.
He participated to several national and international projects (European project FP7 EULER, COST 295 DYNAMO, Anillo en Redes, ANR AGAPE, ANR DIMAGREEN, ANR STINT, etc.) and is currently the principal investigator of the Inria Associated team AlDyNet (2013-2018). He has academic collaborations with Brazil, Canada, Chile, Greece, Italy, Japan and Norway, and with companies such as Alcatel-Lucent and Amadeus.
    报告摘要：Tree-decompositions of graphs are a way to study and model topological structure of graphs. Such decompositions have many applications for designing algorithms that allow to efficiently solve difficult (NP-hard in general) problems in graphs (e.g., coloring, dominating set, cover...). The classical approach consists in decomposing graphs in small “pieces” (subsets of vertices) that may be organized along the minimal separators of the graph. Another approach is to minimize metric properties of these pieces instead of their size. For instance, minimizing the bags' diameter (resp., radius) correspond to the tree-length (resp. tree-breadth) We survey some recent results on the computational complexity of these parameters and their relationship with the treewidth of graphs.
This is based on joint works with D. Coudert, G. Ducoffe and S. Legay