During the fifth year of the AlDyNet associated team between COATI and the Universidad Adolfo Ibáñez (Santiago, Chile), we have pursued ongoing research on the computation of graph properties related to hyperbolicity or graph convexity.
We have also worked on optimization problems having applications in wireless backhaul network, among others, to provide connectivity for wireless communications in buses or urban trains.
Finally, we have progressed in our implementations and simulations on the properties of the geographical network of Santiago.
 On graph parameters.
Gromov hyperbolicity is a graph parameter reflecting the metric structure of a graph. While this parameter can be computed in polynomialtime (supercubic in the size of the graph), existing algorithms are not efficient for large graphs (thousand of vertices). We proposed an algorithm which is efficient in practice [1]. Hyperbolicity has important practical effects for routing in graphs [2], we also considered this aspect via particular embeddings of graphs [3]. Besides, we have also continued our work on graph convexity [4] that we started last year through AlDyNet.
Graph parameters have an impact on the behavior (timecomplexity) of algorithms for many problems. The theory of Parameterized complexity intends to formalize it through the design of Fixed Parameter Tractable algorithms (roughly, given a parameter k and on input of size n, an algorithm is FPT if its timecomplexity is f(k)nO(1) for some computable function). Mostly NPhard problems have been studied via this approach and, only recently, researchers have started to address problems in P. We also contributed to this hot topic [5].  On graph decompositions. Graph decompositions are a way to decompose graphs into small pieces (subsets of nodes) that are arranged in order to preserve the connectivity properties. They are widely used by dynamic programming algorithms (divide and conquer) in order to solve efficiently graph problems that are difficult in general. One prerequisite for running this kind of algorithms is the computation of good graph decompositions, which itself is a NPhard problem.
We have focused on the computation of treedecompositions with minimum number of pieces [6]. Precisely, the maximum size of a piece being fixed, we aim at finding a decomposition of a graph minimizing the number of such pieces. This problem appears to be NPhard in general graphs and the case of trees is still open [6].
We also have worked on pathdecompositions through their algorithmic interpretation, namely the Graph searching. Roughly, in Graph searching, we aim at computing the minimum number of mobile agents necessary to capture an invisible arbitrary fast intruder. A strategy of such a team of agents is equivalent to a pathdecomposition of the graph. We consider a variant of Graph searching where two agents cannot occupy a vertex simultaneously [7]. This leads to the first model of Graph Searching whose complexity differs from the complexity of the classical model [8].
We finally consider Graph Searching in a distributed setting [9], extending some previous work of the members of AlDyNet.  Optimization in telecommunication networks. We have considered several telecommunication networks such as PairtoPair or wireless networks.
We have studied live distributed streaming systems in which a source diffuses a content to peers via a tree, a node forwarding the data to its children. Such systems are subject to a high churn, peers frequently joining and leaving the system. We propose and analyze simple localized algorithm to repair the diffusion tree to allow an efficient data distribution [10]. N. Nisse will do a seminar on this topic at University Adolfo Ibañez on November 21st 2017.
We also pursued our study on the reliability of backhaul networks. we provide an algorithm to compute the exact reliability of a backhaul network, given a discrete probability distribution on the possible capacities available at each link. We also have studied the impact of some specific routing constraints (e.g., monorouting, load balancing, stretch) on the design and reliability of the networks [11].
Finally, our previous work on the disconnection of a moving vehicle from a linear Wireless access network has been published in an international revue [12].  On Eternal Domination in graphs. During the visit of Karol Suchan (February 2017), we have mainly worked on a game on graphs introduced by members of AlDyNet [13] (Fionn Mc Inerney will do a seminar on this topic at University Adolfo Ibañez on November 23rd 2017). This game is closely related to Dominating sets in graph (a set of vertices is a dominating set if every vertex of the graph either belong to this set or is a neighbor of an element of this set) and Eternal Domination. We will continue this study during the visit of COATI members to University Adolfo Ibañez (November 17th to December 1st, 2017).
 Optimization in geographical networks We aim at considering transportation networks of mediumsize cities in order to see the performances of various routing or graph algorithms on them. During the Master internship of Marko Oleksiyenko, we have extracted data of the city of Nice (mainly from OpenStreetMap) and applied to it the hublabeling algorithm of Kosowski and Viennot (Inria Paris) [14]. A way to obtain better performances is to partition such a network into smaller cells. We have used Linear Programme for this purpose. However, we think that our work on graph Domination (at some distance) may help to obtain different (possibly better) partitions
Publications 2017
 Nathann Cohen, David Coudert, Guillaume Ducoffe, and Aurélien Lancin. Applying cliquedecomposition for computing Gromov hyperbolicity. Theoretical Computer Science, Elsevier, 2017, 690, pp.114139
 Sahel Sahhaf, Wouter Tavernier, Dimitri Papadimitriou, Davide Careglio, Alok Kumar, Christian Glacet, David Coudert, Nicolas Nisse, Lluis Fàbrega, Pere Vilà, Miguel Camelo, Pieter Audenaert, Didier Colle, Piet Demeester. Routing at Large Scale: Advances and Challenges for Complex Networks. IEEE Network, Institute of Electrical and Electronics Engineers, 2017, pp.12 – 22.
 David Coudert and Guillaume Ducoffe. A simple approach for lowerbounding the distortion in any Hyperbolic embedding. European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’17), Electronic Notes in Discrete Mathematics, 61, pp.293 – 299, 2017.
 Kolja Knauer, Nicolas Nisse. Computing metric hulls in graphs. Research Report] Inria – Sophia Antipolis. 2017

Lélia Blin, Janna Burman and Nicolas Nisse. Exclusive Graph Searching.
Algorithmica, Volume 77(3), pages 942969, 2017. 
Euripides Markou, Nicolas Nisse and Stéphane Pérennes. Exclusive Graph Searching vs. Pathwidth.
Information and Computation, Volume 252, pages 243260, 2017 
Gianlorenzo D’Angelo, Alfredo Navarra and Nicolas Nisse. Gathering and Exclusive Searching on Rings under Minimal Assumptions.
Distributed Computing, Volume 30(1), pages 1748, 2017.  Frédéric Giroire, Remigiusz Modrzejewski, Nicolas Nisse and Stéphane Pérennes, Maintaining Balanced Trees For Structured Distributed Streaming Systems. Discrete Applied Maths 232: 176188 (2017).
 David Coudert, James Luedtke, Eduardo Moreno and Konstantinos Priftis. Computing and maximizing the exact reliability of wireless backhaul networks. In proceedings of International Network Optimization Conference (INOC), https://hal.inria.fr/hal01394593, 2017.
 Nathann Cohen, Fionn McInerney, Nicolas Nisse and Stéphane Pérennes. Study of a combinatorial game in graphs through Linear Programming. To appear in Proceedings of 28th International Symposium on Algorithms and Computation (ISAAC), 2017.
 Marko Oleksiyenko, Bicycleoriented itinerary computation for smart cities. Master thesis, Univ. Nice Sophia Antipolis, MarchAugust, 2017.
Visits in 2017
 Chile to France
 Karol Suchan: February 10th to 25th, 2017.
 France to Chile
 David Coudert: November 17th to December 1st, 2017.
D. Coudert gave a seminar on November 30th, 2017 at Univ. Adolfo Ibáñez, on the Flinders Hamiltonian Cycle Problem Challenge.  Fionn Mc Inerney: November 17th to December 1st, 2017.
F. Mc Inerney gave a seminar on November 23rd, 2017 at Univ. Adolfo Ibáñez, on Spy Games in Graphs.  Nicolas Nisse: November 17th to December 1st, 2017.
N. Nisse gave a seminar on November 21st, 2017 at Univ. Adolfo Ibáñez, on Maintaining Balanced Trees For Structured Distributed Streaming Systems.
 David Coudert: November 17th to December 1st, 2017.