Bi Li (李碧) is recipient of the Chinese government award for outstanding selffinanced students abroad, edition 2014, for her PhD thesis entitled “Tree Decompositions and Routing Problems“. Congratulation !
More details can be found here and here (in chinese).
Tag: PhD & HDR
PhD defense of Alvinice Kodjo
 Title: “Design and Optimization of Wireless Backhaul Networks”
 When: December 18, 2014 — 14:30
 Where: PolytechNice Sophia Antipolis, salle E+131 (Amphi Gradiné Templiers 2)
 Committee:
 Dritan Nace (Referee), Heudiasyc, UTC Compiègne, France
 Hervé Rivano (Referee), CITI, Inria, INSA Lyon, Université de Lyon, Villeurbanne, France
 Patrick Beatini 3Roam, Sophia Antipolis, France
 David Coudert (supervisor), COATI, Inria/I3SUNS, France
 Brigitte Jaumard Concordia Univ., Montréal, Canada
 Philippe Michelon, LIA, Université d’Avignon et des Pays de Vaucluse, France

Abstract: The main work of this thesis focuses on the wireless backhaul networks. This type of network has the advantage of allowing rapid and easy deployment at relatively low costs while offering capacity of up to 1Gbps over links of a hundred of kilometers. We studied different optimization problems in such networks that represent real challenges for industrial sector.
The first issue addressed in this thesis concerns the capacity allocation on the links at minimum cost. It was solved by a linear programming approach with column generation. Our method solves the problems on large size networks. In addition, we quickly obtain very good quality solutions.
We then studied the problem of network infrastructure sharing between virtual operators. The objective is to maximize the revenue of the operator of the physical infrastructure while satisfying the demands (constraints of quality of service) of virtual operators customers of the network. In this context, we proposed a model to the problem using mixed integer linear programming. Our formulation is robust to changes in traffic demands of virtual operators.
Another operational expenditure in this type of network is the energy consumption. Many operators are now seeking to reduce network energy consumption, both by using more efficient equipments and by using more appropriate routing solutions. We proposed a robust energyaware routing solution for the network. The proposed model is based on backbone networks, but it can easily be adapted to wireless back haul networks. Our solution was formulated using a mixed integer linear program. We also proposed heuristics to find efficient solutions for large networks.
The last work of this thesis focuses on cognitive radio networks and more specifically on the problem of bandwidth sharing. We formalized it using a linear program with a different approach to robust optimization. This model differs from other cases of robust optimization discussed above by the position of the uncertain terms in the model. We based our solution on the 2stage linear robust formulation proposed by Michel Minoux.
This thesis was carried out in partnership with the SME 3ROAM (http://www.3roam.com) and in collaboration with various researchers from different universities in the world. It was cofunded by the PACA province and the SME 3ROAM. 
Keywords: Backhaul networks, Wireless networks, Operations Research, Robust optimization.
PhD defense of Aurélien Lancin
 Title: "Study of complex networks properties for the optimization of routing models"
 When: December 9, 2014  10:30
 Where: Conference room of I3S
 Committee:
 JeanClaude Konig (Referee), LIRMM, Montpellier, France
 Bruno Quoitin (Referee), Univ. Mons, Belgium
 Laurent Viennot (Referee), Inria & LIAFA, Paris France
 David Coudert (supervisor), COATI, Inria/I3SUNS, France
 Dimitri Papadimitriou, AlcatelLucent Bell, Antwerp, Belgium
 Guillaume UrvoyKeller I3S, Univ. Nice Sophia Antipolis, France

Abstract:This thesis considers routing issues in networks, and particularly the graph of the autonomous systems (AS) of the Internet. Firstly, we aim at better understanding the properties of the Internet that are useful in the design of new routing paradigms. Secondly, we want to evaluate by simulation the performance of these paradigms. The first part of my work concerns the study of the Gromov hyperbolicity, a useful metric property for the design of new routing paradigms. I show how to use a decomposition of the graph by cliqueseparators as a preprocessing method for the computation of the hyperbolicity. Then, I propose a new algorithm to compute this property. Altogether, these methods allows us for computing the hyperbolicity of graphs up to 58 000 nodes. The second part of my work concerns the development of DRMSim, a new Dynamic Routing Model Simulator. It facilitates the evaluation of the performances of various routing schemes and their comparison to the standard routing scheme of the Internet, the border router protocol BGP. Using DRMSim, we performed simulations of several compact routing schemes on topologies up to O(10k) nodes. I describe its architecture and detail some examples. Then, I present a feasibility study for the design of a parallel/distributed version of DRMSim in order to simulate BGP on larger topologies.

Keywords:Internet, Algorithm, Graph, Hyperbolicity, Graph decomposition, Routing, BGP, Simulation, Parallel Distributed Simulation.
PhD defense of Bi LI
 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.
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.