PhD defense of Bi LI

PhD 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:
  • 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 NP-hard 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 polynomial-time algorithm that either returns an induced cycle of length at least k + 1 of a graph G or compute a k-good 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 k-good tree decompositions.
    In Chapter 5, we consider the prize collecting Steiner tree problem (a generalization of the Steiner-tree 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 polynomial-time 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

PhD 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:
  • 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 NP-complete and polynomial-time 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 NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, we use different algorithmic tools for proving polynomial-time solvability of certain instances, some of them involving relatively complicated algorithms. The techniques vary from easy brute force algorithms, algorithms based on maximum-flow 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 Erdos-Pó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

PhD 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:
  • Abstract: In this thesis, we study several models of energy-aware routing. For each model, we present a linear programming formulation to find the exact solution. Moreover, since energy-aware routing is NP-hard problem, we also propose efficient heuristic algorithms for large scale networks.
    In the first part of this thesis, we deal with GreenRE – a new energy-aware routing model with the support of redundancy elimination. We first present a deterministic model in which we show how to combine energy-aware 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 end-users, we limit the changes in network configurations in multi-period traffic matrices in Open Shortest Path First (OSPF) protocol. Next, we address the problem of limited rule space in OpenFlow switches when installing energy-aware routing configurations.
    Finally, we present in the appendix other works developed during this thesis: multicast network protocol and TCP congestion control algorithm.

  • Keywords: Energy-aware Routing, Redundancy Elimination, Open Shortest Path First, Software Defined Networks.

HDR defense of Nicolas Nisse

HDR Nicolas Nisse

  • Title: “Algorithmic complexity, Between Structure and Knowledge: How Pursuit-evasion Games help”
  • When: May 26, 2014 — 14:30
  • Where: Room Euler Violet, Inria Sophia Antipolis Méditerranée
  • Committee:
  • 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 Pursuit-Evasion 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 turn-by-turn Pursuit-Evasion 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 Pursuit-Evasion 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.

DRMSim: A Routing-Model Simulator for Large-Scale Networks

DRMSim architecture

by: Aurélien Lancin (COATI) and Dimitri Papadimitriou (Alcatel-Lucent Bell labs)
In ERCIM news 94, pp 31-32, 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 large-scale, 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 state-full routing. For this purpose, we introduce DRMSim a Dynamic Routing Model simulator of routing models on large-scale networks. (read more)