 Title: “Tree Decompositions and Routing Problems”
 When: November 12, 2014 — 10:00
 Where: Room Euler Violet, Inria Sophia Antipolis – Méditerranée
 Committee:
 Pascal Berthomé (Referee), LIFO, Univ. Orléans & INSA CentreVal de Loire, France
 Nicolas Hanusse (Referee), CNRS, Bordeaux University, France
 David Coudert (cosupervisor), COATI, Inria/I3SUNS, France
 Hao Li, LRI, CNRS, France
 Jérôme Galtier, Orange Labs, France
 Nicolas Nisse (cosupervisor), COATI, Inria/I3SUNS, France
 Igor Litovsky, I3S, Univ. Nice Sophia Antipolis, France

Abstract: A tree decomposition of a graph is a way to represent it as a tree by preserving some connectivity properties of the initial graph. Tree decompositions have been widely studied for their algorithmic applications, in particular using dynamic programming approach. In this thesis, we study tree decompositions satisfying various constraints and design algorithms to compute them in some graph classes. We then use tree decompositions or specific graph properties to solve several problems related to routing. The thesis is divided into two parts.
In the first part, we study tree decompositions satisfying some properties. In Chapter 2, we investigate minimum size tree decompositions, i.e., with minimum number of bags. Given a fixed k ≥ 4, we prove it is NPhard to compute a minimum size decomposition with width at most k in the class of graphs with treewidth at least 4. We design polynomial time algorithms to compute minimum size tree decompositions in some classes of graphs with treewidth at most 3 (including trees). Part of these results will be presented in ICGT 2014.
In Chapter 3, we study the chordality (longest induced cycle) of graphs and introduce the notion of good tree decomposition (where each bag must satisfy some particular structure). Precisely, we study the Cops and Robber games in graphs with no long induced cycles. Our main result is the design of a polynomialtime algorithm that either returns an induced cycle of length at least k + 1 of a graph G or compute a kgood tree decomposition of G. These results have been published in ICALP 2012 and Algorithmica.
In the second part of the thesis, we focus on routing problems. In Chapter 4, we design a compact routing scheme that achieves good performance in the class of graphs admitting kgood tree decompositions.
In Chapter 5, we consider the prize collecting Steiner tree problem (a generalization of the Steinertree problem with weighted nodes and edges). We design two risk models of the problem when the weights are given as intervals. In these models, we design polynomialtime algorithms for graphs with small treewidth. These results have been published in AAIM 2010 and the journal Acta Mathematicae Applicatae Sinica.
Finally, in Chapter 6, we consider the gathering problem in grids and in presence of interferences. We design approximation algorithms (up to small additive constants depending on the interferences) for solving this problem. This work is in revision for TCS. 
Keywords: Tree Decomposition, Compact Routing Scheme, Prize Collecting Steiner Tree, Gathering.
Author: David COUDERT
PhD defense of Ana Karolinna Maia de Oliveira
 Title: “Subdivisions of Digraphs”
 When: November 5, 2014 — 10:00
 Where: Room Euler Violet, Inria Sophia Antipolis – Méditerranée
 Committee:
 Stéphane Bessy (Referee), LIRMM Montpellier, France
 Frédéric Havet (Supervisor), COATI, Inria/I3SUNS, France
 Frédéric Maffray, Laboratoire GSCOP, Grenoble, France
 Adrien Richard, I3S (CNRS/UNS), Sophia Antipolis, France
 Nicolas Trotignon (Referee), ENS Lyon, France
 Yann Vaxès, LIF, UFR Sciences Luminy, France

Abstract: In this work, we consider the following problem: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We believe that there is a dichotomy between NPcomplete and polynomialtime solvable instances of this problem. We present many examples of both cases. In particular, except for five instances, we are able to classify all the digraphs F of order 4. While all NPhardness proofs are made by reduction from some version of the 2linkage problem in digraphs, we use different algorithmic tools for proving polynomialtime solvability of certain instances, some of them involving relatively complicated algorithms. The techniques vary from easy brute force algorithms, algorithms based on maximumflow calculations, handle decompositions of strongly connected digraphs, among others.
Finally, we treat the very special case of F being the disjoint union of directed cycles. In particular, we show that the directed cycles of length at least 3 have the ErdosPósa Property: for every n, there exists an integer tn such that for every digraph D, either D contains n disjoint directed cycles of length at least 3, or there is a set T of tn vertices that meets every directed cycle of length at least 3. From this result, we deduce that if F is the disjoint union of directed cycles of length at most 3, then one can decide in polynomial time if a digraph contains a subdivision of F. 
Keywords: Digraphs, subdivisions.
PhD defense of Truong Khoa Phan
 Title: “Design and Management of Networks with Low Power Consumption”
 When: September 25, 2014 — 10:00
 Where: Room Euler Violet, Inria Sophia Antipolis – Méditerranée
 Committee:
 Bernardetta Addis, Ecole des mines de Nancy, France
 Edoardo Amaldi (Referee), Politecnico di Milano, Italy
 David Coudert (cosupervisor), COATI, Inria/I3SUNS, France
 Arie M.C.A. Koster, RWTH Aachen, Germany
 Laurent Lefèvre (Referee), Inria, Lyon, France
 Joanna Moulierac (cosupervisor), COATI, Inria/I3SUNS, France
 Guillaume UrvoyKeller, I3S, Univ. Nice Sophia Antipolis, France

Abstract: In this thesis, we study several models of energyaware routing. For each model, we present a linear programming formulation to find the exact solution. Moreover, since energyaware routing is NPhard problem, we also propose efficient heuristic algorithms for large scale networks.
In the first part of this thesis, we deal with GreenRE – a new energyaware routing model with the support of redundancy elimination. We first present a deterministic model in which we show how to combine energyaware routing and redundancy elimination to improve energy efficiency for backbone networks. Then, we extend the model in order to take into account uncertainties in traffic volumes and redundancy rates.
The second part of this thesis is devoted to the deployment issues of energy aware routing in practice. In detail, to avoid service deterioration for endusers, we limit the changes in network configurations in multiperiod traffic matrices in Open Shortest Path First (OSPF) protocol. Next, we address the problem of limited rule space in OpenFlow switches when installing energyaware routing configurations.
Finally, we present in the appendix other works developed during this thesis: multicast network protocol and TCP congestion control algorithm. 
Keywords: Energyaware Routing, Redundancy Elimination, Open Shortest Path First, Software Defined Networks.
HDR defense of Nicolas Nisse
 Title: “Algorithmic complexity, Between Structure and Knowledge: How Pursuitevasion Games help”
 When: May 26, 2014 — 14:30
 Where: Room Euler Violet, Inria Sophia Antipolis Méditerranée
 Committee:
 Victor Chepoi, LIF, AixMarseille Université
 David Coudert, Inria, Univ. Nice Sophia Antipolis, I3S, CNRS
 Fedor V. Fomin, University of Bergen, Norway
 Pierre Fraigniaud, CNRS, LIAFA, Univ. Paris Diderot
 Cyril Gavoille (Rapporteur), LaBRI, Université de Bordeaux
 JeanCharles Régin, I3S, Univ. Nice Sophia Antipolis
 Dimitrios M. Thilikos (Rapporteur), CNRS, LIRMM, Univ. Montpellier et Dept. of Maths., Univ. Athens
 Peter Widmayer (Rapporteur), ETH Zurich, Switzerland

Abstract: This manuscript describes the work I did since I obtained my Ph.D. in 2007. In addition to the presentation of my contributions, I tried to give overviews of the scientific areas my work takes part of and some of the main issues that arise here.
My work deals with new algorithmic challenges posed by the growth of nowadays networks and by the increased data and traffic arising in it. One way to cope with the size of these problems is to use the particular network structures. For this, I strive to develop new characterizations of graph structural properties in order to calculate and use them efficiently for an algorithmic perspective. Whenever possible, I propose distributed algorithms
that are based only on a local/partial knowledge of networks.
In particular, I study the PursuitEvasion games – dealing with the capture of a mobile entity by a team of other agents – that offer an interesting perspective on many properties of graphs and, in particular, decompositions of graphs. This approach from mobile agents point of view also allows the study of various applications in telecommunication networks and of some distributed computing models.
Chapter 1 is dedicated to the study of several variants of turnbyturn PursuitEvasion Games, mostly to the Cops and Robber games. Chapter 2 focuses on graph decompositions and their relationship with graph searching. Chapter 3 treats another aspect of PursuitEvasion games with a study of variants of Graph Searching games, both in centralized and distributed settings. Finally, Chapter 4 deals with routing problems in various environments and with distributed models of computation.
Ecole ResCom 2014
Ecole d’été du pôle ResCom du GDR ASR, ResCom 2014
 Main topic: Network Science
 When: May 1216, 2014
 Where: Furiani, Corsica, France
 Link: conference website
GRASTA 2014
6th Workshop on GRAph Searching, Theory and Applications (GRASTA 2014)
 When: March 31 – April 4, 2014
 Where: Cargèse, Corsica, France
 Contact: Nicolas Nisse (organizing chair)
 Link: conference website
JCALM
14th Journées Combinatoire et Algorithmes du Littoral Méditerranéen (JCALM)
 Main topic: graph minors
 When: October 1516, 2013
 Where: Barcelona, Spain
 Link: conference website
DRMSim: A RoutingModel Simulator for LargeScale Networks
by: Aurélien Lancin (COATI) and Dimitri Papadimitriou (AlcatelLucent Bell labs)
In ERCIM news 94, pp 3132, July 2013
The expansion of Internet topology, which comprises thousands of Autonomous Systems (AS), has resulted in a number of important research challenges. The Border Gateway Protocol (BGP), which is used to make core routing decisions on the Internet, starts to show its limitations in terms of the number of routing table entries it can store locally, update in a timely fashion and dynamically exchange. Because it is impractical to deploy newly designed routing protocols on the Internet a largescale, simulation is an unavoidable step to validate their properties. However, the increasing routing information processing (CPU) and storage (memory) introduces similar challenges for the simulation of statefull routing. For this purpose, we introduce DRMSim a Dynamic Routing Model simulator of routing models on largescale networks. (read more)
OPODIS 2013
17th International Conference On Principles Of DIstributed Systems (OPODIS 2013)
 When: December 1618, 2013
 Where: Nice, France
 Contact: Nicolas Nisse (organizing chair)
 Link: conference website
 Submission deadline: Sunday June 23
DRMSim training workshop
This tutorial session, organized in the context of the FP7 EULER project, aims at explaining how to install and setup DRMSim to perform experiments, and how to develop its own routing model and metrics.
 When: March 46, 2013
 Where: INRIA SophiaAntipolis – Méditerranée
 Contact: Aurélien Lancin
 Link: workshop website (restricted access)