报告题目：Recovery of disrupted airline operations using k-Maximum Matching in graphs
报告人：Nicolas NISSE 研究员 法国信息与自动化研究所(Inria Sophia Antipolis)
照片：

邀请人：李碧
报告时间：2018年9月12日10:00
报告地点：信远楼II206williamhill威廉希尔官网报告厅
报告人简介：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.
报告摘要：We study a graph theoretical problem for helping Airline Operation Controllers. Given a graph G and a matching M, the goal is to compute a maximum matching that can be achieved from M by augmenting paths of length at most k, where k is a fixed odd integer. We prove that the problem is polynomial for k at most 3. Then, we show it s NP-complete for k at least 5, in the class of planar bipartite graphs with maximum degree 3. Then, we further investigate this problem (and the other related problem where augmenting paths must have length exactly k) in trees.
This is based on joint works with Julien Bensmail, Valentin Garnero, Alexandre Salchs and Valentin Weber