COATI - 2021 - Annual activity report

COATI

COATI - 2021

2021

Activity report

Project-Team

COATI

RNSR: 201322124W

Research center

Sophia Antipolis - Méditerranée

In partnership with:

CNRS, Université Côte d'Azur

Combinatorics, Optimization and Algorithms for Telecommunications

In collaboration with:

Laboratoire informatique, signaux systèmes de Sophia Antipolis (I3S)

Domain

Networks, Systems and Services, Distributed Computing

Theme

Networks and Telecommunications

Creation of the Project-Team: 2013 January 01

Keywords

Computer Science and Digital Science

A1.2.1. Dynamic reconfiguration
A1.2.3. Routing
A1.2.5. Internet of things
A1.2.9. Social Networks
A1.6. Green Computing
A3.5.1. Analysis of large graphs
A7.1. Algorithms
A7.1.1. Distributed algorithms
A7.1.3. Graph algorithms
A8.1. Discrete mathematics, combinatorics
A8.2. Optimization
A8.2.1. Operations research
A8.7. Graph theory
A8.8. Network science
A9.7. AI algorithmics
A9.9. Distributed AI, Multi-agent

1 Team members, visitors, external collaborators

Research Scientists

David Coudert [Team leader, Inria, Senior Researcher, HDR]
Ramon Aparicio Pardo [Univ Côte d'Azur, Researcher, HDR]
Jean-Claude Bermond [CNRS, Emeritus, HDR]
Christelle Caillouet [Univ Côte d'Azur, Researcher]
Frédéric Giroire [CNRS, Senior Researcher, HDR]
Frédéric Havet [CNRS, Senior Researcher, HDR]
Emanuele Natale [CNRS, Researcher]
Nicolas Nisse [Inria, Researcher, HDR]
Stéphane Pérennes [CNRS, Senior Researcher, HDR]

Faculty Members

Julien Bensmail [Univ Côte d'Azur, Associate Professor, HDR]
Alexandre Caminada [Univ Côte d'Azur, Professor]
Joanna Moulierac [Univ Côte d'Azur, Associate Professor]
Michel Syska [Univ Côte d'Azur, Associate Professor]
Chuan Xu [Univ Côte d'Azur, Associate Professor, from Sep 2021]

Post-Doctoral Fellows

François Pirot [Inria, until Aug 2021]
Malgorzata Sulkowska [Univ Côte d'Azur]

PhD Students

Ali Al Zoobi [Inria]
Arthur Carvalho Walraven Da Cunha [Inria]
Giuseppe Di Lena [Orange Labs, CIFRE, until Mar 2021]
Igor Dias Da Silva [Inria]
Thomas Dissaux [Univ Côte d'Azur]
Foivos Fioravantes [Univ Côte d'Azur]
Adrien Gausseran [Univ Côte d'Azur, until Oct 2021]
Hicham Lesfari [Univ Côte d'Azur]
Zhejiayu Ma [Easybroadcast, CIFRE]
Thi Viet Ha Nguyen [Inria]
Lucas Picasarri Arrieta [Univ Côte d'Azur, from Sep 2021]
Thibaud Trolliet [Univ Côte d'Azur, until Aug 2021]
Francesco d'Amore [Inria]

Technical Staff

Luc Hogie [CNRS, Engineer]

Interns and Apprentices

Hugo Boulier [Inria, from May 2021 until Jul 2021]
Fedi Ghalloussi [Inria, from May 2021 until Jul 2021]
Gregory Hoareau [CNRS, from Mar 2021 until Sep 2021]
Imane Houbbane [Millionroads, from Mar 2021 until Aug 2021]
Cyprien Michel-Deletie [École Normale Supérieure de Lyon, from May 2021 until Jul 2021]
Kostiantyn Ohulchanskyi [Univ Côte d'Azur, from Mar 2021 until Aug 2021]
Nacim Oijid [École Normale Supérieure de Lyon, from Apr 2021 until Jun 2021]
Pierre Pebereau [Inria, from Jul 2021 until Aug 2021]
Marcello Politi [Inria, from Mar 2021 until Jun 2021]
Juliette Schabanel [École Normale Supérieure de Paris, from Jun 2021 until Jul 2021]
Sofiia Shelest [Univ Côte d'Azur, from Mar 2021 until Aug 2021]

Administrative Assistant

Patricia Riveill [Inria]

Visiting Scientist

Redha Abderrahmane Alliche [Univ Côte d'Azur]

External Collaborator

Michel Cosnard [Univ Côte d'Azur, HDR]

2 Overall objectives

Coati is a joint team between INRIA Sophia Antipolis - Méditerranée and the I3S laboratory (Informatique Signaux et Systèmes de Sophia Antipolis) which itself belongs to CNRS (Centre National de la Recherche Scientifique) and Univ. Côte d'Azur. Its research fields are Algorithmics, Discrete Mathematics, and Combinatorial Optimization, with applications mainly in telecommunication networks.

The main objectives of the Coati project-team are to design networks and communication algorithms. In order to meet these objectives, the team studies various theoretical problems in Discrete Mathematics, Graph Theory, Algorithmics, and Operations Research and develops applied techniques and tools, especially for Combinatorial Optimization and Computer Simulation. In particular, Coati used in the last years both these theoretical and applied tools for the design of various networks, such as SDN (software defined networks), WDM, wireless (radio), satellite, and peer-to-peer networks. This research has been done within various industrial and international collaborations.

Coati also investigates other application areas such as bio-informatics and transportation networks.

The research done in Coati results in the production of prototypes and more advanced software, and in the contribution to large open source software such as Sagemath.

3 Research program

Since its creation in 2013, the objectives of Coati are to conduct fundamental research in Discrete Mathematics, Graph Theory, Digraph Theory, Algorithms and Operations Research, and to use these tools for studying specific network optimization problems. Notice that we are mostly interested in telecommunications networks. However, our expertise can be applied to solve many other problems in various areas (transport, biology, resource allocation, social sciences, smart-grids, speleology, etc.) and we collaborate with teams of these other domains. Coati also contributes to the development of software components in order to validate proposed algorithms and to boost their dissemination.

The research program of Coati is therefore structured as follows.

We conduct fundamental research in graph and digraph theory. Our goal is to better understand the structure of (di)graphs and which particular (sub)structures make an optimization problem on (di)graphs difficult. We are particularly interested in digraphs which are less investigated than (undirected) graphs, although most optimization problems are naturally modeled using digraphs. This is certainly due to the fact that several problems that can be solved in polynomial time on graphs are hard to solve on digraphs.
We use this knowledge to design algorithms on (di)graphs (exact, sub-exponential, parameterized, approximation, heuristics) in order to solve various optimization problems. We also investigate games on graphs as an algorithmic counterpart of some (di)graph theory studies to get more insight on problems and (di)graphs properties. One of the challenges we have to face in the design of algorithms is the increase in size of practical instances. It is difficult, if not impossible, to solve practical instances optimally using existing tools. Therefore, we have to find new ways to address problems using reduction and decomposition methods, characterization of polynomial instances (which are sometimes the practical ones), or design of algorithms with acceptable practical performances independently of the worst case time complexity.
We study specific network optimization problems at both design and management levels such as energy efficiency in networks, routing reconfiguration of optical and software defined networks (SDN), placement and migration of chains of virtual functions (NFV), compact routing in large-scale networks, deployment and management of fleet of drones, design of reliable wireless networks, evolution of the routing in case of any kind of topological modifications (maintenance operations, failures, capacity variations, ...), survivability to single and multiple failures, ... These specific problems often come from questions of our industrial partners (CIENA, Huawei, Orange labs). We first contribute to the modeling of these problems; then we either use existing tools or develop new tools in Operation Research and (Di)Graph Theory to solve them.
We also investigate optimization problems in other application fields (see Section 7.4) such as structural biology, transportation networks, economy, sociology, etc. For instance, we collaborate in Structural Biology with the Inria project-team ABS (Algorithms Biology Structure) from Sophia Antipolis. In the area of intelligent transport systems, we collaborate with the SMEs BeNomad and Instant-System on routing problems in multi-modal transportation systems. We also collaborate with GREDEG (research center in economics, law, and management) and the SKEMA business school on the analysis of the impact of competitive funding on the evolution of scientific networks.

On the one side, these collaborations benefit to the considered domains via the dissemination of our tools. On the other side, they give rise to new problems of interest for our community, and help us to improve our knowledge and to test our algorithms on specific instances.
Last but not the least, the research done in Coati results in the production of software (Grph, BigGrph, etc.), and in the contribution to large open source softwares such as Sagemath.

Note also that beside our research activity, we are deeply involved in the dissemination of our domain towards a general public.

4 Application domains

4.1 Telecommunication Networks

Coati is mostly interested in telecommunications networks but also in the network structure appearing in social, molecular and transportation networks.

We focus on the design and management of heterogeneous physical and logical networks. The project has kept working on the design of backbone networks (optical networks, radio networks, IP networks). However, the fields of Software Defined Networks and Network Function Virtualization are growing in importance in our studies. In all these networks, we study routing algorithms and the evolution of the routing in case of any kind of topological modifications (maintenance operations, failures, capacity variations, etc.).

4.2 Other Domains

Our combinatorial tools may be well applied to solve many other problems in various areas (transport, biology, resource allocation, chemistry, smart-grids, speleology, etc.) and we collaborate with experts of some of these domains.

For instance, we collaborate with project-team ABS (Algorithms Biology Structure) from Sophia Antipolis on problems from Structural Biology (co-supervision of a PhD student). In the area of transportation networks, we collaborate with SMEs Benomad and Instant-System on dynamic car-pooling combined with multi-modal transportation systems in the context of ANR project Multimod started in January 2018. We collaborate with SME MillionRoads since October 2019 on the modeling and exploration of the HumanRoads database that gathers more than 100 million curriculums (studies and career paths of persons). Last, we have started a collaboration with GREDEG (Groupe de Recherche en Droit, Economie et Gestion, Université Côte d'Azur) and the SKEMA business school on the analysis of the impact of competitive funding on the evolution of scientific collaboration networks.

5 Highlights of the year

5.1 Awards

Małgorzata Sulkowska
- Primus award for publications in distinctive scientific journals from the Wrocław University of Science and Technology, Poland.
- Secundus award for the best young computer scientists at the Wrocław University of Science and Technology, Poland.

6 New software and platforms

Let us desribe new/updated software.

6.1 New software

6.1.1 FastGRACE

Keywords:
Graph algorithmics, Java, Data Exploration, Data base
Functional Description:

Modeling of a database linking users to their studies and careers in the form of a graph. Algorithms for graphs associated with the queries made (of the type: number of users who have completed a given curriculum, distribution of careers following a given curriculum, distribution of curriculums preceding a given career, etc.). Scaling for a database of >100 million users.

In addition, Neo4j implemetations of various algorithms tested on the HumanRoads data.
Contact:
Nicolas Nisse
Participants:
Nicolas Chleq, Frédéric Giroire, Luc Hogie, Nicolas Nisse

6.1.2 Graph Hyperbolicity

Keywords:
Graph algorithmics, Algorithm engineering, Gromov hyperbolicity
Scientific Description:
Hyperbolicity is a graph parameter related to how much a graph resembles a tree with respect to distances. Its computation is challenging as the main approaches consist in scanning all quadruples of the graph or using fast matrix multiplication as building block, both are not practical for large graphs. This software implements state-of-the-art algorithms and in particular new algorithms enabling to compute the hyperbolicity of graphs with unprecedented size (up to a million nodes) and speeds up the computation of previously attainable graphs.
Functional Description:
Implementation in C++ of algorithms for computing the hyperbolicity of graphs.
URL:
https://gitlab.inria.fr/dcoudert/hyperbolicity
Publications:
hal-03431155, hal-03201405, hal-03438325
Contact:
David Coudert
Participants:
David Coudert, André Nusser, Laurent Viennot

6.1.3 k shortest simple paths

Name:
k shortest simple paths
Keywords:
Graph, Graph algorithmics
Functional Description:
Implementation in C++ of algorithms for computing the k shortest simple paths from a source to a destination in a weighted directed graph.
Release Contributions:
This version implements the standard algorithm proposed by Yen (Yen), Node Classification algorithm proposed by Feng (NC), the Sidetrack Based algorithm proposed by Kurz and Mutzel (SB), and variants of SB proposed by Al Zoobi, Coudert and Nisse to reduce running time (SB*) and memory usage (PSB). It also implements the PNC algorithm proposed by Al Zoobi, Coudert and Nisse to reduce the execution time of the NC algorithm.
URL:
https://gitlab.inria.fr/dcoudert/k-shortest-simple-paths
Publications:
hal-02865918, hal-03196830, hal-03438331
Contact:
David Coudert
Participants:
David Coudert, Nicolas Nisse, Ali Al Zoobi

6.1.4 SageMath

Name:
SageMath
Keywords:
Graph algorithmics, Graph, Combinatorics, Probability, Matroids, Geometry, Numerical optimization
Scientific Description:
SageMath is a free open-source mathematics software system. It builds on top of many existing open-source packages: NumPy, SciPy, matplotlib, Sympy, Maxima, GAP, FLINT, R and many more. Access their combined power through a common, Python-based language or directly via interfaces or wrappers.
Functional Description:

SageMath is a free mathematics software system written in Python and combining a large number of mathematical libraries under a common interface.

INRIA teams contribute in different ways to the software collection. COATI adds new graph algorithms along with their documentations and the improvement of underlying data structures. LFANT contributes through libraries such as ARB and PARI/GP, and directly through SageMath code for algebras and ring and field extensions.
Release Contributions:
See http://www.sagemath.org/changelogs/
URL:
http://www.sagemath.org/
Contact:
David Coudert
Participants:
David Coudert, Xavier Caruso

6.1.5 JMaxGraph

Keywords:
Java, HPC, Graph algorithmics
Functional Description:
JMaxGraph is a collection of techniques for the computation of large graphs on one single computer. The motivation for such a centralized computing platform originates in the constantly increasing efficiency of computers which now come with hundred gigabytes of RAM, tens of cores and fast drives. JMaxGraph implements a compact adjacency-table for the representation of the graph in memory. This data structure is designed to 1) be fed page by page, à-la GraphChi, 2) enable fast iteration, avoiding memory jumps as much as possible in order to benefit from hardware caches, 3) be tackled in parallel by multiple-threads. Also, JMaxGraph comes with a flexible and resilient batch-oriented middleware, which is suited to executing long computations on shared clusters. The first use-case of JMaxGraph allowed F. Giroire, T. Trolliet and S. Pérennes to count K2,2s, and various types of directed triangles in the Twitter graph of users (23G arcs, 400M vertices). The computation campaign took 4 days, using up to 400 cores in the NEF Inria cluster.
URL:
http://www.i3s.unice.fr/~hogie/software/?name=jmaxgraph
Contact:
Luc Hogie

6.1.6 Idawi

Keywords:
Java, Distributed, Distributed computing, Distributed Applications, Web Services, Parallel computing, Component models, Software Components, P2P, Dynamic components, Iot
Functional Description:

Idawi is a middleware for the development and experimentation of distributed algorithms. It boasts a very general and flexible multi-hop component-oriented model that makes it applicable in many contexts such as parallel and distributed computing, cloud, Internet of Things (IOT), P2P networks. Idawi components can be deployed anywhere a SSH connection is possible. They exhibit services which communicate with each other via explicit messaging. Messages can be sent synchronously or asynchronously, and can be handled in either a procedural (with the optional use of futures) or reactive (event-driven) fashion. In the latter case, multi-threading is used to maximize both the speed and the number of components in the system. Idawi message transport is done via TCP, UDP, SSH or shared-memory.

Idawi is a synthesis of past developments of the COATI Research group in the field of graph algorithms for big graphs, and it is designed to be useful to the current and future Research project of COATI and KAIROS team-projects.
URL:
https://github.com/lhogie/idawi
Contact:
Luc Hogie

6.1.7 OnlineGraph

Keywords:
Java, Distributed computing, Graph algorithmics
Functional Description:
OnlineGraph is a cloud graph library. It consists of a (HTTP) server (based on Idawi) which exposes a set of (Web) services for the storage, the manipulation and the graphical rendering of graphs.
URL:
https://github.com/lhogie/OnlineGraph
Contact:
Luc Hogie

7 New results

7.1 Network Design and Management

Network design is a very wide subject which concerns all kinds of networks. In telecommunications, networks can be either physical (backbone, access, wireless, ...) or virtual (logical). The objective is to design a network able to route a (given, estimated, dynamic, ...) traffic under some constraints (e.g. capacity) and with some quality-of-service (QoS) requirements. Usually the traffic is expressed as a family of requests with parameters attached to them. In order to satisfy these requests, we need to find one or several paths between their end-nodes. The set of paths is chosen according to the technology, the protocol or the QoS constraints.

The last years have been very lively for networks with the rises of several new paradigms like Software Defined Networks (SDN) and Network Function Virtualization (NVF), of new technologies like 5G, Elastic Optical Networks or LoRa, and of new usages like Internet of Things, 5G, High quality video streaming. All these changes have brought or renewed a large number of algorithmic and optimization problems for the design and management of networks. In this context, our work has mainly focused on the study of three types of problems:

How to build scalable routing solutions for SDN?
How to efficiently route and place virtual resources in networks using NFV?
How to use efficiently wireless networks?

This very wide topic is considered by a lot of academic and industrial teams in the world. Our approach is to attack these problems with tools from operations research and discrete mathematics (some of them developed in our teams, see Sections 7.2 and 7.3). This approach is shared by a number of other teams worldwide, e.g. UFC and UNIFOR (Fortaleza, Brazil), Concordia Univ. (Montréal, Canada), Univ. Adolfo Ibañez (Santiago, Chile), Univ. Oran (Algeria), with which we have a direct collaboration.

7.1.1 Network slicing and Network Function Virtualization

Participants: Giuseppe Di Lena, Adrien Gausseran, Frédéric Giroire, Hicham Lesfari, Joanna Moulierac, Stéphane Pérennes.

Recent advances in networks such as Software Defined Networking (SDN) and Network Function Virtualization (NFV) are changing the way network operators deploy and manage Internet services. On the one hand, SDN introduces a logically centralized controller with a global view of the network state. On the other hand, NFV enables the complete decoupling of network functions from proprietary appliances and runs them as software applications on general purpose servers. In such a way, network operators can dynamically deploy Virtual Network Functions (VNFs). SDN and NFV, both separately, bring to network operators new opportunities for reducing costs, enhancing network flexibility and scalability, and shortening the time-to-market of new applications and services. Moreover, the centralized routing model of SDN jointly with the possibility of instantiating VNFs on demand may open the way for an even more efficient operation and resource management of networks. For instance, an SDN/NFV-enabled network may simplify the Service Function Chain (SFC) deployment and provisioning by making the process easier and cheaper. We addressed several questions in this context.

Reconfiguration of slices

In collaboration with Brigitte Jaumard (Concordia University, Montréal, Canada), we consider in 37, 36 the problem of network slice reconfiguration without interruption. A network slice can be seen as a virtual network embedded on the physical topology, with some VNFs placed in specific nodes. As an example, a simplified network slice could be an SFC (as in 37). Reconfiguring from time to time network slices allows to reduce the network operational costs and to increase the number of slices that can be managed within the network. However, it impacts users' Quality of Service during the reconfiguration step. To solve this issue, we study solutions implementing a make-before-break scheme. We propose new models and scalable algorithms (relying on column generation techniques in 36) that solve large data instances in few seconds.

Protection against failures

In collaboration with Chidung Lac (Orange labs), we investigate in 53 on the protection against failures of VNF deployments. We use a representation of the VNFs as a set of VNF components (VNFCs). These VNFCs are typically designed with a redundancy scheme and need to be deployed against failures of, e.g., compute servers, and must be such deployed with respect a particular resiliency mechanism for protection purposes. Therefore, choosing an efficient mapping of VNFCs to the compute servers is a challenging problem in the optimization of the software-defined, virtualization-based next generation of networks. In 53, we model the problem of reliable VNFCs placement under anti-affinity constraints using several optimization techniques. A novel approach based on an extension of bin packing is proposed. We perform a comprehensive evaluation in terms of performance under real-world ISP networks along with synthetic traces. We show that our methods can calculate rapidly efficient solutions for large instances.

In collaboration with Chidung Lac (Orange labs), Damien Saucez and Thierry Turletti (DIANA), and Issam Tahiri, Ruslan Sadykov and François Vanderbeck (RealOpt), we consider in 41 a path-based protection scheme with the global rerouting strategy in which, for each failure situation, there may be a new routing of all the demands. Our optimization task is to minimize the needed amount of bandwidth. After discussing the hardness of the problem, we develop two scalable mathematical models that we handle using both Column Generation and Benders Decomposition techniques. Through extensive simulations on real-world IP network topologies and on randomly generated instances, we show the effectiveness of our methods: they lead to savings of 40 to 48% of the bandwidth to be installed in a network to protect against failures compared to traditional schemes. Finally, our implementation in OpenDaylight demonstrates the feasibility of the approach. Its evaluation with Mininet shows that our solution provides sub-second recovery times, but the way it is implemented may greatly impact the amount of signaling traffic exchanged. In our evaluations, the recovery phase requires only a few tens of milliseconds for the fastest implementation, compared to a few hundreds of milliseconds for the slowest one.

Emulation of SDN networks

Mininet is the most popular tool when it comes to evaluate SDN propositions. Mininet allows to emulate SDN networks on a single computer but shows its limitations with resource intensive experiments as the emulating host may become overloaded. To tackle this issue, we propose Distrinet 31, a distributed implementation of Mininet over multiple hosts, based on LXD/LXC, Ansible, and VXLAN tunnels. Distrinet uses the same API than Mininet, meaning that it is compatible with Mininet programs. It is generic and can deploy experiments on Linux clusters (e.g., Grid'5000), as well as on the Amazon EC2 cloud platform.

In 49 we propose and implement a new placement module for distributed emulation of SDN/NFV emulation. To handle the ever growing demand of resource intensive experiments distributed, network emulation tools such as Mininet and Maxinet have been proposed. They automatically allocate experimental resources. However, we have shown that resources are poorly allocated, leading to resource overloading and hence to dubious experimental results. This is why we propose and implement a new placement module for distributed emulation. Our algorithms take into account both link and node resources and minimize the number of physical hosts needed to carry out the emulation. Through extensive numerical evaluations, simulations, and actual experiments , we show that our placement methods outperform existing ones and allowing to re-establish trust in experimental results.

This work has been done in collaboration with Chidung Lac (Orange labs) and Damien Saucez and Thierry Turletti (DIANA).

7.1.2 Optical networks

Participants: David Coudert.

Make-before-break reoptimization in optical networks

Optical multilayer optimization periodically reorganizes layer 0-1-2 network elements to handle both existing and dynamic traffic requirements in the most efficient manner. This delays the need for adding new resources in order to cope with the evolution of the traffic, thus saving capex (capital expenditure).

In collaboration with Brigitte Jaumard and Huy Duong (Concordia Université, Montréal, Canada) and Armolavicius, Romualdas (Ciena), we focussed in 34 on Layer 2, i.e., on capacity reoptimization at the optical transport network (OTN) layer when routes (e.g., LSPs in MPLS networks) are making unnecessarily long detours to evade congestion. Reconfiguration into optimized routes can be achieved by re-defining the routes, one at a time, so that they use the vacant resources generated by the disappearance of services using part of a path that transits the congested section. To maintain the Quality of Service, it is desirable to operate under a Make-Before-Break (MBB) paradigm, with the minimum number of reroutings. The challenge is to determine the best rerouting order while minimizing the bandwidth requirement. We propose an exact and scalable optimization model for computing a minimum bandwidth rerouting scheme subject to MBB in the OTN layer of an optical network. Numerical results show that we can successfully apply it on networks with up to 30 nodes, a very significant improvement with respect to the state of the art. We also provide some reoptimization analysis in terms of the bandwidth requirement vs. the number of reroutings.

In collaboration with Brigitte Jaumard and Huy Duong (Concordia Université, Montréal, Canada), we revisited in 52 MBB rerouting with the objective of identifying the reroute sequence planning that minimizes the number of reroutes in order to minimize the resource usage. We propose a Dantzig-Wolfe decomposition mathematical model to solve this complex rerouting problem. We investigate how multiple or parallel rerouting reduces the overall minimum number of rerouting events (shortest makespan), and achieve the best resource usage. Numerical results bring interesting insights on that question and show a computational time reduction by about one order of magnitude over the state of the art.

Dantzig-Wolfe Decomposition for the Design of Filterless Optical Networks

Filterless optical networks use passive splitters and combiners with coherent optics, providing wavelength selection in the digital domain, while forming a passive fiber-tree topology between nodes. In collaboration with Brigitte Jaumard and Yan Wang (Concordia Université, Montréal, Canada), we investigate in 38 the optimal design of filterless optical networks while minimizing the number of required wavelengths. We propose a Dantzig-Wolfe decomposition model in which each subproblem aims to generate a potential filterless optical subnetwork, with a directed tree topology. The master problem then selects the best combination of subnetworks. Numerical experiments demonstrate significant performance improvement over previous work, reducing previous computational results by a factor of 2 to 10 depending on the size of the data instances.

7.1.3 Optimization of LoRa networks for the IoT

Participants: Christelle Caillouet.

LoRa is a low-power and long range radio communication technology designed for low-power Internet of Things devices. These devices are often deployed in remote areas where the end-to-end connectivity provided through one or more gateways may be limited. In collaboration with Dimitrios Zorbas, Khaled Abdelfadeel Hassan and Dirk Pesch (Tyndall National Institute, Irland), we examine in 43 the case where the gateway is not available at all times. As a consequence, the sensing data need to be buffered locally and transmitted as soon as a gateway becomes available. However, due to the Aloha-style transmission policy of current LoRa-based standards, such as the LoRaWAN, delivering a large number of packets in a short period of time by a large number of nodes becomes impossible. To avoid bursts of collisions and expedite data collection, we propose a time-slotted transmission scheduling mechanism.We formulate the data scheduling optimisation problem, taking into account LoRa characteristics, and compare its performance to low complexity heuristics. Moreover, we conduct a set of simulations to show the benefits of synchronous communications on the data collection time and the network performance.

In collaboration with Martin Heusse and Franck Rousseau (Drakkar, LIG, Grenoble), we propose in 57 an optimization model for single-cell LoRaWAN planning which computes the limit range of each spreading factor (SF) in order to maximize the minimum packet delivery ratio (PDR) of every node in the network. It allows to balance the opposite effects of attenuation and collision of the transmissions and guarantee fairness among the nodes.

7.1.4 Optimizing drone coverage

Participants: Christelle Caillouet, David Coudert, Igor Dias da Silva.

The use of autonomous unmanned aerial vehicles (UAVs) or drones has emerged to efficiently collect data from mobile sensors when there is no infrastructure available. The drones can form a flying ad-hoc network through which the sensors can send their data to a base station at any time.

In 50, we address the data collection problem using the minimum number of unmanned aerial vehicles (UAVs) in a disaster management scenario where mobile sensors are investigating the devastated area. Critical information needs to be quickly gathered for processing by the rescue team, so the use of UAVs in this situation is of great interest. We propose an optimal model for computing the trajectories of the UAVs while guaranteeing the total coverage of the ground mobile sensors and connectivity among the UAVs with a central base station dedicated to data processing. Our model is based on a decomposition model and is solved effectively using column generation. We show that we can provide a plan for deploying the UAVs minimizing the total traveled distance.

7.1.5 Optimizing the exchange of data

Participants: Giuseppe Di Lena, Frédéric Giroire, Hicham Lesfari, Zhejiayu Ma.

Peer-to-peer networks

Live streaming traffic represents an increasing part of the global IP traffic. Hybrid CDN-P2P architectures have been proposed as a way to build scalable systems with a good Quality of Experience (QoE) for users, in particular, using the WebRTC technology which enables real-time communication between browsers and, thus, facilitates the deployment of such systems. An important challenge to ensure the efficiency of P2P systems is the optimization of peer selection. Most existing systems address this problem using simple heuristics, e.g. favor peers in the same ISP or geographical region. In collaboration with Soufiane Roubia (EasyBroadcast) and Guillaume Urvoy-Keller (I3S), we analyzed in 54 9 months of operation logs of a hybrid CDN-P2P system and demonstrate the sub-optimality of those classical strategies. Over those 9 months, over 18 million peers downloaded over 2 billion video chunks. We propose learning-based methods that enable the tracker to perform adaptive peer selection. Furthermore, we demonstrate that our best models, which turn out to be the neural network models can (i) improve the throughput by 22.7%, 14.5%, and 6.8% (reaching 89%, 20.4%, and 24.3% for low bandwidth peers) over random peer, same ISP, and geographical selection methods, respectively (ii) reduce by 18.6%, 18.3%, and 16% the P2P messaging delay and (iii) decrease by 29.9%, 29.5%, and 21.2% the chunk loss rate (video chunks not received before the timeout that triggers CDN downloads), respectively.

Cloud networks

Many companies and organizations are moving their applications from on-premises data centers to the cloud. The cloud infrastructures can potentially provide an infinite amount of computation (e.g., Elastic Compute) and storage (e.g., Simple Service Storage). In addition, all cloud providers propose different offers: IaaS, PaaS, and SaaS. The demo 96, done in collaboration with Chidung Lac (Orange labs) and Thierry Turletti (DIANA), focuses on the IaaS services, presenting a simple tool to measure the network delay in a virtual infrastructure built entirely in the cloud. These measurements are useful for organizations that are moving current applications to, or creating new applications in, the cloud, but have requirements on the maximum, or average, network delay that these applications can tolerate. We present CloudTrace, a simple CLI tool that creates regional and multiregional experiments to measure delay, using Amazon AWS.

Traffic monitoring and anomaly detection

With the continuous growing level of dynamicity, heterogeneity, and complexity of traffic data, anomaly detection remains one of the most critical tasks to ensure an efficient and flexible management of a network. Recently, driven by their empirical success in many domains, especially bioinformatics and computer vision, graph kernels have attracted increasing attention. Our work aims at investigating their discrimination power for detecting vulnerabilities and distilling traffic in the field of networking. In 59, we propose Nadege, a new graph-based learning framework which aims at preventing anomalies from disrupting the network while providing assistance for traffic monitoring. Specifically, we design a graph kernel tailored for network profiling by leveraging propagation schemes which regularly adapt to contextual patterns. Moreover, we provide provably efficient algorithms and consider both offline and online detection policies. Finally, we demonstrate the potential of kernel-based models by conducting extensive experiments on a wide variety of network environments. Under different usage scenarios, Nadege significantly outperforms all baseline approaches.

7.2 Graph Algorithms

In the last years, Coati has conducted an intense research effort on the algorithmic aspects of graph theory. We are mainly interested in designing efficient algorithms for large graphs and in understanding how structural properties of networks can help for this purpose. In general we try to find the most efficient algorithms, either exact algorithms or approximation ones, to solve various problems of graph theory, often with applications in telecommunication networks. We are involved in many international and national collaborations with academic and industrial partners.

We mainly focus on four topics: efficient computation of graph parameters, graph decompositions, combinatorial games in graphs and distributed computing.

We use graph theory to model various network problems. We study their complexity with the aim of identifying the key structural properties of graphs that make these problems hard or easy. We then search for the most efficient algorithms to solve the problems, sometimes focusing on specific graph classes from which the problems are polynomial-time solvable. Our algorithms are generally implemented (e.g., in Sagemath) and tested on real-life networks (e.g., road networks, Twitter, graph of co-publications from Scopus, etc.).
Tree-Decompositions are the corner-stone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. We propose different approaches, based on a pursuit-evasion perspective or on metric aspects of graphs, to compute optimal or approximate tree-decompositions of graphs.
One important topic of Coati is the study of combinatorial games in graphs. For instance, we are strongly involved in the organization of GRASTA dedicated to pursuit-evasion games (and their relationships with tree-decompositions) and games in graphs (special issues 102, 99, organization of the 10th edition of GRASTA in May 2022...). We study combinatorial games for themselves by determining their complexity but also because they provide nice models for problems arising in telecommunication networks (e.g., localization games).
Within the research area of the theory of distributed computing, Coati investigates the recent topics of computational dynamics on complex networks, namely the study of algorithmically-simple interaction rules among agents represented by nodes of a complex network. Such systems are of interest in many scientific areas, ranging from biology to sociology. We contribute to this research endeavour by focusing on the fundamental coordination problems, in which agents are required to agree on a configuration which satisfies some condition based on their initial input state.

7.2.1 Complexity of graph problems

Participants: Ali Al Zoobi, David Coudert, Thomas Dissaux, Foivos Fioravantes, Nicolas Nisse.

Treelength of series-parallel graphs

The length of a tree-decomposition of a graph is the maximum distance between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up to a factor less than $\frac{3}{2}$ (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the maximum size of its isometric cycles. This work initiates the study of treelength in planar graphs by considering the next natural superclass of outerplanar graphs, namely the one of series-parallel graphs.

In collaboration with Guillaume Ducoffe (Université Politehnica, Bucarest, Roumanie) and Simon Nivelle (INSPÉ Paris), we first fully describe in 51, 58 the treelength of melon graphs (set of pairwise internally disjoint paths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up to a factor $\frac{3}{2}$ in series-parallel graphs. Our main result is a polynomial-time algorithm for deciding whether a series-parallel graph has treelength at most 2. Our latter result relies on a characterization of series-parallel graphs with treelength 2 in terms of infinite families of forbidden isometric subgraphs.

The $k$ shortest simple paths problem with dissimilarity constraints

The similarity between two paths can be measured according to the proportion of arcs they share. We study the complexity of several variants of the problem of computing “dissimilar" paths (whose measure of similarity does not exceed a certain threshold) between two given vertices of a weighted directed graph. For four of the most studied measures in the literature, we give in 71, 55 a unified and simple proof of the fact that finding $k$ shortest dissimilar paths is NP-Complete. We then consider the problem of finding an alternative to one or more given paths. We show that finding a path that is dissimilar to another given path can be done in polynomial time for one of the four considered measures while it is NP-Complete for the three remaining measures. In addition, we show that if $k = 2$ paths are given, finding a new path that is dissimilar to the given ones is NP-Complete even on DAGs for the four considered measures. Moreover, for the four considered measures, we show that if a path $P$ is given, finding a shortest path among those that are dissimilar to $P$ is NP-Complete in DAGs.

Complexity of finding maximum locally irregular induced subgraphs

If a graph $G$ is such that no two adjacent vertices of $G$ have the same degree, we say that $G$ is locally irregular. In collaboration with Nikolaos Melissinos (LAMSADE, Université Paris-Dauphine) and Theofilos Triomatis (School of Electrical Engineering, University of Liverpool), we introduce and study in 84 the problem of identifying a largest induced subgraph of a given graph $G$ that is locally irregular. Equivalently, given a graph $G$ , find a subset $S$ of $V (G)$ of minimum order, such that by deleting the vertices of $S$ from $G$ results in a locally irregular graph; we denote with $I (G)$ the order of such a set $S$ . We first treat some easy graph families, namely paths, cycles, trees, complete bipartite and complete graphs. However, we show that the decision version of the introduced problem is NP-Complete, even for restricted families of graphs, such as subcubic bipartite, or cubic graphs.

Then, looking for more positive results, we turn towards computing the parameter $I (G)$ through the lens of parameterised complexity. In particular, we provide two algorithms that compute $I (G)$ , each one considering different parameters. The first one considers the size of the solution $k$ and the maximum degree $Δ$ of $G$ with running time ${(2 Δ)}^{k} n^{O (1)}$ , while the second one considers the treewidth $t w$ and $Δ$ of $G$ , and has running time $Δ^{2 t w} n^{O (1)}$ . Therefore, we show that the problem is FPT by both $k$ and $t w$ if the graph has bounded maximum degree $Δ$ . Since these algorithms are not FPT for graphs with unbounded maximum degree (unless we consider $Δ + k$ or $Δ + t w$ as the parameter), it is natural to wonder about the existence of an algorithm that does not include additional parameters (other than $k$ or $t w$ ) in its dependency. We manage to settle negatively this question, and we show that our algorithms are essentially optimal. In particular, we prove that there is no algorithm that computes $I (G)$ with dependence $f (k) n^{o (k)}$ or $f (t w) n^{o (t w)}$ , unless the ETH fails.

7.2.2 Combinatorial games in graphs

Participants: Julien Bensmail, Jean-Claude Bermond, Foivos Fioravantes, Hicham Lesfari, Nicolas Nisse, Thi Viet Ha Nguyen, Stéphane Pérennes, Malgorzata Sulkowska.

Eternal domination game on graphs

In the eternal domination game played on graphs, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices on their turn. The goal is to determine the eternal domination number $γ_{a l l}^{\infty}$ of a graph, which is the minimum number of guards required to defend against an infinite sequence of attacks.

We have continued the study of the eternal domination game on strong grids. Cartesian grids have been vastly studied with tight bounds for small grids such as $2 \times n$ , $3 \times n$ , $4 \times n$ , and $5 \times n$ grids, and it was proven in 103 that the eternal domination number of these grids in general is within $O (m + n)$ of their domination number which lower bounds the eternal domination number. Furthermore, it has been proved in 101 that the eternal domination number of strong grids is upper bounded by $\frac{m n}{6} + O (m + n)$ .

In 39, we prove that, for all $n, m \in ℕ^{*}$ such that $m \geq n$ , $⌊ \frac{n}{3} ⌋ ⌊ \frac{m}{3} ⌋ + Ω (n + m) = γ_{a l l}^{\infty} (P_{n} ⊠ P_{m}) = ⌈ \frac{n}{3} ⌉ ⌈ \frac{m}{3} ⌉ + O (m \sqrt{n})$ (note that $⌈ \frac{n}{3} ⌉ ⌈ \frac{m}{3} ⌉$ is the domination number of $P_{n} ⊠ P_{m}$ ). We then generalize our technique to prove that $γ_{a l l}^{\infty} (G) = γ (G) + o (γ (G))$ for all graphs $G \in ℱ$ , where $ℱ$ is a large family of $D$ -dimensional grids which are supergraphs of the $D$ -dimensional Cartesian grid and subgraphs of the $D$ -dimensional strong grid. In particular, $ℱ$ includes both the $D$ -dimensional Cartesian grid and the $D$ -dimensional strong grid.

Protection numbers in simply generated trees and Pólya trees

The protection number of a tree is the length of the shortest path from the root to a leaf. It is interchangeably called the protection number of the root. We define the protection number of a vertex $v$ in tree $T$ as the protection number of a maximal subtree of $T$ having $v$ as its root. In collaboration with Bernhard Gittenberger (Technische Universität Wien, Austria), Isabella Larcher (Technische Universität Wien, Austria) and Zbigniew Gołębiewski (Wrocław University of Science and Technology, Poland), we determine in 40 the limit of the expected value and the variance of the protection number of the root in simply generated trees, in Pólya trees, and in unlabelled non-plane binary trees, when the number of vertices tends to infinity. Moreover, we compute expectation and variance of the protection number of a randomly chosen vertex in all those tree classes. We obtain exact formulas as sum representations, where the obtained sums are rapidly converging thus allowing an efficient numerical computation of high accuracy.

The largest connected subgraph game

In collaboration with Fionn Mc Inerney (Technical University of Denmark), we have introduced in 75, 56, 44 the largest connected subgraph game played on an undirected graph $G$ . In each round, Alice first colours an uncoloured vertex of $G$ red, and then, Bob colours an uncoloured vertex of $G$ blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than the order of any blue (red, resp.) connected subgraph.

We have first proved that Bob can never win, and define a large class of graphs (called reflection graphs) in which the game is a draw. We have then showed that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that recognising reflection graphs is GI-hard. We have also proved that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we have given an algorithm to determine the outcome of the game in cographs in linear time.

The vertex-capturing game

Inspired by the board game Kahuna, we have introduced and studied in 79, in collaboration with Fionn Mc Inerney (Technical University of Denmark), a new 2-player scoring game played on graphs called the vertex-capturing game. The game is played on a graph by two players, Alice and Bob, who take turns colouring an uncoloured edge of the graph. Alice plays first and colours edges red, while Bob colours edges blue. The game ends once all the edges have been coloured. A player captures a vertex if more than half of its incident edges are coloured by that player, and the player that captures the most vertices wins.

Using classical arguments from the field, we have first proved general properties of this game. Namely, we have proved that there is no graph in which Bob can win (if Alice plays optimally), while Alice can never capture more than 2 more vertices than Bob (if Bob plays optimally). Through dedicated arguments, we have then investigated more specific properties of the game, and have focused on its outcome when played in particular graph classes. Specifically, we have determined the outcome of the game in paths, cycles, complete bipartite graphs, and Cartesian grids, and have given partial results for trees and complete graphs.

Bootstrap percolation and the game of life

Let $r \geq 1$ be any non negative integer and let $G = (V, E)$ be any undirected graph in which a subset $D \subseteq V$ of vertices are initially infected. In collaboration with Fabricio Benevides (Federal University of Ceará, Brasil), we consider in 72 the process in which, at every step, each non-infected vertex with at least $r$ infected neighbours becomes infected and an infected vertex never becomes non-infected. The problem consists in determining the minimum size $s_{r} (G)$ of an initially infected vertices set $D$ that eventually infects the whole graph $G$ . This problem is closely related to cellular automata, to percolation problems and to the Game of Life studied by John Conway. Note that $s_{1} (G) = 1$ for any connected graph $G$ . The case when $G$ is the $n \times n$ grid, $G_{n \times n}$ , and $r = 2$ is well known and appears in many puzzle books, in particular due to the elegant proof that shows that $s_{2} (G_{n \times n}) = n$ for all $n \in ℕ$ . We study the cases of square grids, $G_{n \times n}$ , and tori, $T_{n \times n}$ , when $r \in {3, 4}$ . We show that $s_{3} (G_{n \times n}) = ⌈ \frac{n^{2} + 2 n + 4}{3} ⌉$ for every $n$ even and that $⌈ \frac{n^{2} + 2 n}{3} ⌉ \leq s_{3} (G_{n \times n}) \leq ⌈ \frac{n^{2} + 2 n}{3} ⌉ + 1$ for any $n$ odd. When $n$ is odd, we show that both bounds are reached, namely $s_{3} (G_{n \times n}) = ⌈ \frac{n^{2} + 2 n}{3} ⌉$ if $n \equiv 5 (mod 6)$ or $n = 2^{p} - 1$ for any $p \in ℕ^{*}$ , and $s_{3} (G_{n \times n}) = ⌈ \frac{n^{2} + 2 n}{3} ⌉ + 1$ if $n \in {9, 13}$ . Finally, for all $n \in ℕ$ , we give the exact expression of $s_{3} (T_{n \times n})$ .

Rikudo is NP-complete

Rikudo is a number-placement puzzle, where the player is asked to complete a Hamiltonian path on a hexagonal grid, given some clues (numbers already placed and edges of the path). In collaboration with Kévin Perrot (Aix Marseille Université), we prove in 88 that the game is complete for NP, even if the puzzle has no hole. When all odd numbers are placed it is in P, whereas it is still NP-hard when all numbers of the form $3 k + 1$ are placed.

Complexity of Games Compendium

Since games and puzzles have been studied under a computational lens, researchers unearthed a rich landscape of complexity results showing deep connections between games and fundamental problems and models in computer science. Complexity of Games (CoG, steven3k.gitlab.io/isnphard-test/) is a compendium of complexity results on games and puzzles. It aims to serve as a reference guide for enthusiasts and researchers on the topic and is a collaborative and open source project that welcomes contributions from the community. Emanuele Natale is both a contributor and an administrator of CoG.

7.2.3 Algorithm engineering

Participants: Ali Al Zoobi, David Coudert, Nicolas Nisse.

Algorithm Engineering is concerned with the design, analysis, implementation, tuning, and experimental evaluation of computer programs for solving algorithmic problems. It provides methodologies and tools for developing and engineering efficient algorithmic codes and aims at integrating and reinforcing traditional theoretical approaches for the design and analysis of algorithms and data structures. This approach is particularly suited when formal analysis pessimistically suggests bounds which are unlikely to appear on inputs of practical interest.

Algorithms for the $k$ shortest simple paths problem

The $k$ shortest simple path problem ( $k$ SSP) asks to compute a set of top- $k$ shortest simple paths from a vertex $s$ to a vertex $t$ in a digraph. Yen (1971) proposed the first algorithm with the best known theoretical complexity of $O (k n (m + n log n))$ for a digraph with $n$ vertices and $m$ arcs. Since then, the problem has been widely studied from an algorithm engineering perspective, and impressive improvements have been achieved. The most noticeable proposals are the node-classification (NC) algorithm (Feng, 2014) and the sidetracks-based (SB) algorithm (Kurz, Mutzel, 2016). The latest offers the best running time at the price of a significant working memory. In 70, we first show how to speed up the SB algorithm using dynamic updates of shortest path trees resulting in a faster algorithm (SB*) with same working memory. We then propose the parsimonious SB (PSB) algorithm that significantly reduces the working memory of SB at the cost of a small increase of the running time. Furthermore, we propose the postponed node classification (PNC) algorithm that combines the best of NC and SB. It offers a significant speed up compared to NC while using the same amount of working memory of NC. Our experimental results on complex networks show that all of the considered algorithms have low working memory, and that the PSB algorithm is the fastest. On road networks, the SB* algorithm is the fastest (on median) among the considered algorithms, but it suffers from a large working memory. The PNC algorithm has comparable running time to SB* on road networks while using the same working memory as NC. The code of all considered algorithms is available online 97.

Then, in collaboration with Arthur Finkelstein (I3S and Instant-System), we have extended in 80 the Yen's and PNC algorithms to find the $k$ earliest arrival time journeys in public transit networks. The proposed PNC-PT algorithm (PNC for public transit networks) is currently the fastest algorithm for solving the problem.

Gromov hyperbolicity

Hyperbolicity is a graph parameter which indicates how much the shortest-path distance metric of a graph deviates from a tree metric. It is used in various fields such as networking, security, and bioinformatics for the classification of complex networks, the design of routing schemes, and the analysis of graph algorithms. Despite recent progress, computing the hyperbolicity of a graph remains challenging. Indeed, the best known algorithm has time complexity $O (n^{3.69})$ , which is prohibitive for large graphs, and the most efficient algorithms in practice have space complexity $O (n^{2})$ . Thus, time as well as space are bottlenecks for computing the hyperbolicity.

In collaboration with André Nusser (MPII, Saarbrücken, Germany) and Laurent Viennot (GANG, Inria Paris), we designed a tool for enumerating all far-apart pairs of a graph by decreasing distances 81, a key component that was previously used to drastically reduce the computation time for hyperbolicity in practice. However, it required the computation of the distance matrix to sort all pairs of nodes by decreasing distance. We proposed a new data structure that avoids this memory bottleneck in practice and for the first time enables computing the hyperbolicity of several graphs with more than 100 000 nodes that were far out-of-reach using previous algorithms. As iterating over far-apart pairs in decreasing order without storing them explicitly is a very general tool, we believe that our approach might also be relevant to other problems.

We then proposed in 47 a new approach that uses a hierarchy of distance- $k$ dominating sets to reduce the search space. This technique, compared to the previous best practical algorithms, enables us to compute the hyperbolicity of graphs with unprecedented size (up to a million nodes) and speeds up the computation of previously attainable graphs by up to 3 orders of magnitude while reducing the memory consumption by up to more than a factor of 23.

The C++ code of all our algorithms is available at 98.

7.2.4 Algorithms for social networks

Participants: Frédéric Giroire, Luc Hogie, Nicolas Nisse, Stéphane Pérennes, Malgorzata Sulkowska, Thibaud Trolliet.

Interest Clustering Coefficient: a New Metric for Directed Networks like Twitter

In 42, we study the clustering of directed social graphs. The clustering coefficient has been introduced to capture the social phenomena that a friend of a friend tends to be my friend. This metric has been widely studied and has been shown to be of great interest to describe the characteristics of a social graph. But, the clustering coefficient is originally defined for a graph in which the links are undirected, such as friendship links (Facebook) or professional links (LinkedIn). For a graph in which links are directed from a source of information to a consumer of information, it is no more adequate. We show that former studies have missed much of the information contained in the directed part of such graphs. We introduce a new metric to measure the clustering of directed social graphs with interest links, namely the interest clustering coefficient. We compute it (exactly and using sampling methods) on a very large social graph, a Twitter snapshot with 505 million users and 23 billion links, as well as other various datasets. We additionally provide the values of the formerly introduced directed and undirected metrics, a first on such a large snapshot. We observe a higher value of the interest clustering coefficient than classic directed clustering coefficients, showing the importance of this metric. By studying the bidirectional edges of the Twitter graph, we also show that the interest clustering coefficient is more adequate to capture the interest part of the graph while classic ones are more adequate to capture the social part. We also introduce a new model able to build random networks with a high value of interest clustering coefficient. We finally discuss the interest of this new metric for link recommendation.

A Random Growth Model with any Real or Theoretical Degree Distribution

The degree distributions of complex networks are usually considered to be power law. However, it is not the case for a large number of them. We thus propose in 60 a new model able to build random growing networks with (almost) any wanted degree distribution. The degree distribution can either be theoretical or extracted from a real-world network. The main idea is to invert the recurrence equation commonly used to compute the degree distribution in order to find a convenient attachment function for node connections-commonly chosen as linear. We compute this attachment function for some classical distributions, as the power-law, broken power-law, geometric and Poisson distributions. We also use the model on an undirected version of the Twitter network, for which the degree distribution has an unusual shape.

Preferential attachment hypergraph with high modularity

Numerous works have been proposed to generate random graphs preserving the same properties as real-life large scale networks. However, many real networks are better represented by hypergraphs. Few models for generating random hypergraphs exist and no general model allows to both preserve a power-law degree distribution and a high modularity indicating the presence of communities. In 85, we present a dynamic preferential attachment hypergraph model which features partition into communities. We prove that its degree distribution follows a power-law and we give theoretical lower bounds for its modularity. We compare its characteristics with a real-life co-authorship network and show that our model achieves good performances. We believe that our hypergraph model will be an interesting tool that may be used in many research domains in order to reflect better real-life phenomena.

In collaboration with Michał Lasoń (Wroclaw University of Science and Technology, Poland), we prove in 92 that a class of graphs with an excluded minor and with the maximum degree sublinear in the number of edges is maximally modular, that is, modularity tends to 1 as the number of edges tends to infinity.

7.2.5 Distributed algorithms

Participants: Francesco D'Amore, Emanuele Natale.

Parallel Lévy walks

In collaboration with George Giakkoupis (WIDE Team, IRISA, Rennes) and Andrea Clementi (Univ. of Rome 2 "Tor Vergata", Rome, Italy), we investigate in 46 a parallel version of the famous Lévy walk stochastic process, the most famous general model of animal movement. More precisely, motivated by the Lévy foraging hypothesis – the premise that various animal species have adapted to follow Lévy walks to optimize their search efficiency – the authors study the parallel hitting time of Lévy walks on the infinite two-dimensional grid. They consider $k$ independent discrete-time Lévy walks, with the same exponent $α \in (1, \infty)$ , that start from the same node, and analyze the number of steps until the first walk visits a given target at distance $ℓ$ . They show that for any choice of $k$ and $ℓ$ from a large range, there is a unique optimal exponent $α_{k, ℓ} \in (2, 3)$ , for which the hitting time is $\tilde{O} (ℓ^{2} / k)$ w.h.p., while modifying the exponent by an $ϵ$ term increases the hitting time by a polynomial factor, or the walks fail to hit the target almost surely. Based on that, they propose a surprisingly simple and effective parallel search strategy, for the setting where $k$ and $ℓ$ are unknown: the exponent of each Lévy walk is just chosen independently and uniformly at random from the interval $(2, 3)$ . This strategy achieves optimal search time (modulo polylogarithmic factors) among all possible algorithms (even centralized ones that know $k$ ). These results should be contrasted with a line of previous work showing that the exponent $α = 2$ is optimal for various search problems. In their setting of $k$ parallel walks, the authors show that the optimal exponent depends on $k$ and $ℓ$ , and that randomizing the choice of the exponents works simultaneously for all $k$ and $ℓ$ .

Phase transitions of the $k$ -majority dynamics in a biased communication model

In collaboration with Hlafo Alfie Mimun and Matteo Quattropani (LUISS, Roma, Italy) and Sara Rizzo (GSSI, L'Aquila, Italy), we analyze in 48 the binary-state (either $R$ or $B$ ) $k$ -majority dynamics in a biased communication model where nodes have some fixed probability $p$ , independent of the dynamics, of being seen in state $B$ by their neighbors. In this setting we study how $p$ , as well as the initial unbalance between the two states, impact on the speed of convergence of the process, identifying sharp phase transitions.

3-majority dynamics

In collaboration with Isabella Ziccardi (UNIVAQ, L'Aquila, Italy), we study in 94 the behavior of the 3-Majority dynamics in presence of noise. Communication noise is a common feature in several real-world scenarios where systems of agents need to communicate in order to pursue some collective task. In particular, many biologically inspired systems that try to achieve agreements on some opinion must implement resilient dynamics that are not strongly affected by noisy communications. In this work, the authors study the popular 3-Majority dynamics, an opinion dynamics which has been proved to be an efficient protocol for the majority consensus problem, in which they introduce a simple feature of uniform communication noise, following 104. They prove that in the fully connected communication network of $n$ agents and in the binary opinion case, the process induced by the 3-Majority dynamics exhibits a phase transition. For a noise probability $p < 1 / 3$ , the dynamics reaches in logarithmic time an almost-consensus metastable phase which lasts for a polynomial number of rounds with high probability. Furthermore, departing from previous analyses, the authors further characterize this phase by showing that there exists an attractive equilibrium value $s_{eq} \in [n]$ for the bias of the system, i.e. the difference between the majority community size and the minority one. Moreover, the agreement opinion turns out to be the initial majority one if the bias towards it is of magnitude $Ω (\sqrt{n log n})$ in the initial configuration. If, instead, $p > 1 / 3$ , no form of consensus is possible, and any information regarding the initial majority opinion is lost in logarithmic time with high probability. Despite more communications per-round are allowed, the 3-Majority dynamics surprisingly turns out to be less resilient to noise than the Undecided-State dynamics proposed in 104, whose noise threshold value is $p = 1 / 2$ .

On some opinion dynamics in multi-agent systems.

The poster 95 by Francesco d'Amore and Emanuele Natale, in collaboration with Emilio Cruciani (University of Salzburg, Austria), has been presented at MOMI2021: Le Monde des Mathématiques Industrielles (Sophia Antipolis, France). Some recent results about opinion dynamics have been summarized: the community detection properties of the 2-Choices dynamics on core-periphery networks, and the phase transition of the Undecided-State dynamics in fully connected networks with uniform communication noise,

7.3 Graph and digraph theory

Coati works mainly on two important topics in graph theory, namely graph colouring and directed graphs (digraphs), as well as on the interaction between the two.

We are putting an effort on understanding better directed graphs and partitioning problems, and in particular colouring problems. We also try to better understand the many relations between orientations and colourings. We study various substructures and partitions in (di)graphs. For each of them, we aim at giving sufficient conditions that guarantee its existence and at determining the complexity of finding it.

7.3.1 Distinguishing labelling problems and the 1-2-3 Conjecture

Participants: Julien Bensmail, Foivos Fioravantes, Nicolas Nisse.

In distinguishing labelling problems, the general goal is, given a graph, to label some of its elements so that some pairs of elements can be distinguished accordingly to some parameter computed from the labelling. Note that this description involves many parameters that can be played with, such as the set of elements to be labelled, the set of labels to be assigned, the set of elements to be distinguished, and the distinguishing parameter computed from the labelling. A notable example is the so-called 1-2-3 Conjecture, which asks whether almost all graphs can have their edges labelled with 1,2,3 so that every two adjacent vertices are distinguished accordingly to their sums of incident labels.

We have recently obtained a number of results, related both to the 1-2-3 Conjecture and related problems. These results stand both as notable progress towards some open questions, and as new problems of independent interest.

In collaboration with Hervé Hocquard, Dimitri Lajou and Éric Sopena (LaBRI, Université de Bordeaux), we have investigated, through several works, the multiplicative version of the 1-2-3 Conjecture. In that variant of the 1-2-3 Conjecture, adjacent vertices are required to be distinguished, through a labelling, by their products of incident labels. The main conjecture here, is due to Skowronek-Kaziów, who conjectured in 2012 that labels $1, 2, 3$ should suffice for (nearly) all graphs. The best result towards that question, proved back in 2012, was that labels $1, 2, 3, 4$ suffice in general.

In 23, we have made many progress towards that Multiplicative 1-2-3 Conjecture, proving that the conjecture holds for 4-colourable graphs, and providing a result that is very close to what is actually conjectured. Later on, in 76, building upon that earlier study, we have come up with a full proof of the Multiplicative 1-2-3 Conjecture. This stands as one of the most important results of the field, in the recent years.

In 77, we have also initiated the study of a list version of the Multiplicative 1-2-3 Conjecture, which is a standard way to generalise colouring/labelling problems. In particular, we conjecture that any list of three labels should permit to design labellings distinguishing adjacent vertices by products. Towards that presumption, we have provided several results and bounds as support.
In a few more works, we have investigated several side aspects of the 1-2-3 Conjecture, resulting in the study of related variants. Notably, interesting questions relate to the labels $1, 2, 3$ , which are at the heart of the conjecture. One can indeed legitimately wonder about the importance of these precise label values, and whether a similar question would still make sense when considering other label values.

For instance, in 26, with Fionn Mc Inerney (CISPA Helmholtz Center for Information Security, Saarbrücken, Germany) and Kasper Lyngsie (Technical University of Denmark), we have investigated the generalisation of existing results with labels $1, 2$ to any pair of odd labels $a, b$ . While our results show that some results adapt naturally, they also highlight that some subtle discrepancies sometimes exist.

With Bi Li and Binlong Li (from Northwestern Polytechnical University and Xidian University, Xi'an, China), we have investigated proper labellings achieving additional constraints, such as minimising the sum of assigned labels 21 or the maximum vertex sum 25, the main point being to understand proper labellings further. From these questions, with Fionn Mc Inerney, we have run into the question of designing proper 3-labellings minimising the number of assigned 3's 20, 45. This last question has led us to also consider, with Fionn Mc Inerney, so-called equitable proper 3-labellings in 19, for which we have provided new results.
In 28, we have investigated the so-called Weak $(2, 2)$ -Conjecture, which, roughly put, stands as a weaker form of the 1-2-3 Conjecture where label 3 is replaced with a pair of two particular labels (through the notion of coloured labels). In particular, we have provided a result that gets very close to what is actually conjectured.
In a last few works, we have also introduced new variants of distinguishing labelling problems, and have provided a few results on them. For instance, in 24, with Bi Li and Binlong Li, we have investigated a variant of proper labellings where one aims, through a labelling, at constructing an injective vertex-colouring (that is, no vertex should have two neighbours with the same sum of incident labels). In 78, with Hervé Hocquard and Pierre-Marie Marcille (ÉNS de Lyon), we have introduced a variant of the 1-2-3 Conjecture where the vertex sums are fetched within a larger radius $r$ , and it is required that vertices at distance at most $r$ from each other must be distinguished. This problem encapsulating the exact 1-2-3 Conjecture (when $r = 1$ ), we have mainly investigated how existing results from the field generalise to larger $r$ 's. Lastly, in 27, with Fionn Mc Inerney we have introduced a few directed variants of the AVD Conjecture, which are, essentially, proper edge-colourings through which adjacent vertices can be distinguished through their sets of incident colours. Notably, we have introduced a general terminology that resulted in the introduction of four new problems, on which we have provided several results.

7.3.2 Graph and digraph colourings

Participants: Julien Bensmail, Foivos Fioravantes, Frédéric Havet.

Colouring digraphs

In 63, 69, with Pierre Aboulker (DI ENS Paris) and Kolja Knauer and Clément Rambaud (Aix Marseille Université), we give bounds on the dichromatic number $\vec{χ} (Σ)$ of a surface $Σ$ , which is the maximum dichromatic number of an oriented graph embeddable on $Σ$ . We determine the asymptotic behaviour of $\vec{χ} (Σ)$ by showing that there exist constants $a_{1}$ and $a_{2}$ such that, $a_{1} \frac{\sqrt{- c}}{log (- c)} \leq \vec{χ} (Σ) \leq a_{2} \frac{\sqrt{- c}}{log (- c)}$ for every surface $Σ$ with Euler characteristic $c \leq - 2$ . We then give more explicit bounds for some surfaces with high Euler characteristic. In particular, we show that the dichromatic numbers of the projective plane $ℕ_{1}$ , the Klein bottle $ℕ_{2}$ , the torus $𝕊_{1}$ , and Dyck's surface $ℕ_{3}$ are all equal to 3, and that the dichromatic numbers of the 5-torus $𝕊_{5}$ and the 10-cross surface $ℕ_{10}$ are equal to 4. We also consider the complexity of deciding whether a given digraph or oriented graph embeddable on a fixed surface is $k$ -dicolourable. In particular, we show that for any fixed surface, deciding whether a digraph embeddable on this surface is 2-dicolourable is NP-complete, and that deciding whether a planar oriented graph is 2-dicolourable is NP-complete unless all planar oriented graphs are 2-dicolourable (which was conjectured by Neumann-Lara).

Colouring decorated graphs

In two works 17, 18 with Sandip Das, Soumen Nandi and Sagnik Sen (from various institutes in India) and Théo Pierron and Éric Sopena (LaBRI, Université de Bordeaux), we have pursued the study of the usual chromatic theory of graphs to the realm of decorated graphs. Namely, we have considered the analogue of the chromatic number for pushable graphs (oriented graphs in which vertices can be pushed at will, i.e., have the direction of their incident arcs reversed) and signed graphs (2-edge-coloured graphs in which vertices can be switched at will, i.e., have the polarity of their incident edges interchanged). We have mainly focused of graphs with bounded maximum degree. Notably, we have managed to determine the exact value of the analogues of the chromatic number for pushable graphs and signed graphs with maximum degree 3.

Generalising the achromatic number to Zaslavsky's colourings of signed graphs

The chromatic number, which refers to the minimum number of colours required to colour the vertices of graphs properly, is one of the most central notions of the graph chromatic theory. Several of its aspects of interest have been investigated in the literature, including variants for modifications of proper colourings. These variants include, notably, the achromatic number of graphs, which is the maximum number of colours required to colour the vertices of graphs properly so that each possible combination of distinct colours is assigned along some edge. The behaviours of this parameter have led to many investigations of interest, bringing to light both similarities and discrepancies with the chromatic number.

73 takes place in a recent trend aiming at extending the chromatic theory of graphs to the realm of signed graphs, and, in particular, at investigating how classic results adapt to the signed context. Most of the works done in that line to date are with respect to two main generalisations of proper colourings of signed graphs, attributed to Zaslavsky and Guenin. Generalising the achromatic number to signed graphs was initiated recently by Lajou, his investigations being related to Guenin's colourings. With François Dross and Éric Sopena (LaBRI, Université de Bordeaux) and Nacim Oijid (LIRIS Lyon) we have pursued this line of research in 73, but with taking Zaslavsky's colourings as our notion of proper colourings. We have studied the general behaviour of our resulting variant of the achromatic number, mainly by investigating how known results on the classic achromatic number generalise to our context. Our results cover, notably, bounds, standard operations on graphs, and complexity aspects.

On ${BMRN}^{*}$ -colouring of planar digraphs

In a recent work 100 motivated by applications for time division multiple access (TDMA) scheduling problems in wireless networks, we have introduced the notion of ${BMRN}^{*}$ -colouring of digraphs, which is a type of arc-colouring with specific colouring constraints.

In 22, we have pursued these investigations on planar digraphs by answering some of the questions left open in 100. We have exhibited planar digraphs needing 8 colours to be ${BMRN}^{*}$ -coloured, thus showing that the upper bound of 100 cannot be decreased in general. We have also generalized the complexity result of 100 by showing that the problem of deciding whether a planar digraph can be $k$ - ${BMRN}^{*}$ -coloured is NP-hard for every $k \in {3, \dots, 6}$ . Finally, we have investigated the connection between the girth of a planar digraph and the least number of colours in its ${BMRN}^{*}$ -colourings.

7.3.3 Graph drawing

Participants: Julien Bensmail.

In the recent studies of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of the complete graph

K_{n}

was found recently. With Alan Arroyo (IST Austria) and Bruce Richter (University of Waterloo, Canada), we have extended this characterization to all graphs in 16, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible.

7.3.4 Substructures in graphs and digraphs

Participants: Frédéric Havet, Malgorzata Sulkowska.

Semi-proper orientation

Motivated by the proper orientations and the 1-2-3 Conjecture, we investigate the semi-proper orientations. A weighted orientation of graph $G$ is a pair $(D, w)$ where $D$ is an orientation of $G$ and $w$ is an arc-weighting $A (D) \to ℕ ∖ {0}$ . A semi-proper orientation is a weighted orientation such that for every two adjacent vertices $u$ and $v$ , $S_{(D, w)} (v) \neq S_{(D, w)} (u)$ , where $S_{(D, w)} (x)$ is the sum of the weights of arcs with head $x$ in $D$ . The semi-proper orientation number of a graph $G$ , denoted by ${\vec{χ}}_{s} (G)$ , is ${min}_{(D, w) \in Γ} {max}_{v \in V (G)} S_{(D, w)} (v)$ , where $Γ$ is the set of all semi-proper orientations of $G$ . Every proper orientation of a graph $G$ is a semi-proper orientation where the weight of each arc is 1. Consequently, we have $χ (G) - 1 \leq {\vec{χ}}_{s} (G) \leq \vec{χ} (G) \leq Δ (G)$ , where $χ (G)$ , $\vec{χ} (G)$ and $Δ (G)$ are the chromatic number, the proper orientation number and the maximum degree of $G$ , respectively.

A semi-proper orientation $(D, w)$ is optimal if ${max}_{v \in V (G)} S_{(D, w)} (v) = {\vec{χ}}_{s} (G)$ . With Ali Dehghan (Carleton University, Canada), we show in 30 that every graph $G$ has an optimal semi-proper orientation $(D, w)$ such that the weight of each arc is 1 or 2. We then give some bounds on the semi-proper orientation number: we show $⌈\frac{Mad (G)}{2}⌉ \leq \vec{χ_{s}} (G) \leq ⌈\frac{Mad (G)}{2}⌉ + χ (G) - 1$ and $⌈\frac{δ^{*} (G) + 1}{2}⌉ \leq \vec{χ_{s}} (G) \leq 2 δ^{*} (G)$ for all graph $G$ , where $Mad (G)$ and $δ^{*} (G)$ are the maximum average degree and the degeneracy of $G$ , respectively. We then deduce that the maximum semi-proper orientation number of a tree is 2, of a cactus is 3, of an outerplanar graph is 4, and of a planar graph is 6. Finally, we consider the computational complexity of associated problems: we show that determining whether $\vec{χ_{s}} (G) = \vec{χ} (G)$ is NP-complete for planar graphs $G$ with $\vec{χ_{s}} (G) = 2$ ; we also show that deciding whether $\vec{χ_{s}} (G) \leq 2$ is NP-complete for planar bipartite graphs $G$ .

Unavoidable subdigraphs in tournaments

A tournament is an orientation of a complete graph. A digraph is $n$ -unavoidable if it is contained (as a subdigraph) in every tournament of order $n$ . It is well-known that only acyclic digraphs can be unavoidable, and that every acyclic digraph of order $n$ is $2^{n - 1}$ -unavoidable. The unavoidability of an acyclic digraph $D$ , denoted by $unvd (D)$ , is the minimum integer $n$ such that $D$ is $n$ -unavoidable. Determining tight upper bounds on the unavoidability of some special classes of acyclic digraphs has been largely studied since the celebrated theorems of Redei (1934) and Camion (1959) which solved the cases of directed paths and cycles, respectively. Special attention has been devoted to oriented trees and Sumner's conjecture (1972) stating that every tree is is $(2 n - 2)$ -unavoidable, and the stronger one due to Havet and Thomassé (2000) stating that every tree tree of order $n$ with $k$ leaves is $(n + k - 1)$ -unavoidable.

With François Dross (LaBRI, Université de Bordeaux), we improve in 33 on the results towards those conjectures. We first prove that every arborescence (tree in which all arcs are directed away from the root) of order $n$ with $k$ leaves is $(n + k - 1)$ -unavoidable. We then prove that every oriented tree of order $n$ ( $n \geq 2$ ) with $k$ leaves is $(\frac{3}{2} n + \frac{3}{2} k - 2)$ -unavoidable and $(\frac{9}{2} n - \frac{5}{2} k - \frac{9}{2})$ -unavoidable, and thus $(\frac{21}{8} n - \frac{47}{16})$ -unavoidable. Finally, we prove that every oriented tree of order $n$ with $k$ leaves is $(n + 144 k^{2} - 280 k + 124 l)$ -unavoidable.

With David Munhá Correia, Nemanja Draganić and Benny Sudakov (ETH Zürich, Switzerland), François Dross (LaBRI, Université de Bordeaux), Jacob Fox (Stanford University, CA, USA), António Girão (Heidelberg University, Germany), Dániel Korándi and Alex Scott (University of Oxford, England) and William Lochet (University of Bergen, Norway), we consider in 32 powers of directed paths. We show that every tournament contains the $k$ -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for the problem in the special case of $k = 2$ , showing that there is always a square of a directed path of length, which is best possible.

All these results were obtained using the notion of median order.

Spanning eulerian subdigraphs in semicomplete digraphs

A digraph is eulerian if it is connected and every vertex has its in-degree equal to its outdegree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltonian cycle. In 86, together with Jørgen Bang-Jensen and Anders Yeo (University of Southern Denmark), we first characterize the pairs $(D, a)$ of a semicomplete digraph $D$ and an arc $a$ such that $D$ has a spanning eulerian subdigraph containing $a$ . In particular, we show that if $D$ is 2-arc-strong, then every arc is contained in a spanning eulerian subdigraph. We then characterize the pairs $(D, a)$ of a semicomplete digraph $D$ and an arc $a$ such that $D$ has a spanning eulerian subdigraph avoiding $a$ . In particular, we prove that every 2-arc-strong semicomplete digraph has a spanning eulerian subdigraph avoiding any prescribed arc. We also prove the existence of a (minimum) function $f (k)$ such that every $f (k)$ -arc-strong semicomplete digraph contains a spanning eulerian subdigraph avoiding any prescribed set of $k$ arcs. We conjecture that $f (k) = k + 1$ and establish this conjecture for $k \leq 3$ and when the $k$ arcs that we delete form a forest of stars. A digraph $D$ is eulerian-connected if for any two distinct vertices $x, y$ , the digraph $D$ has a spanning $(x, y)$ -trail. We prove that every 2-arc-strong semicomplete digraph is eulerian-connected. All our results may be seen as arc analogues of well-known results on hamiltonian paths and cycles in semicomplete digraphs.

Counting embeddings of rooted trees into families of rooted trees

The number of embeddings of a partially ordered set $S$ in a partially ordered set $T$ is the number of subposets of $T$ isomorphic to $S$ . If both $S$ and $T$ have only one unique maximal element, we define good embeddings as those in which the maximal elements of $S$ and $T$ overlap. With Bernhard Gittenberger and Isabella Larcher (Technische Universität Wien, Austria), and Zbigniew Gołębiewski (Wroclaw University of Science and Technology, Poland), we investigate in 89 the number of good and all embeddings of a rooted poset $S$ in the family of all binary trees on $n$ elements considering two cases: plane (when the order of descendants matters) and non-plane. Furthermore, we study the number of embeddings of a rooted poset $S$ in the family of all planted plane trees of size $n$ . We derive the asymptotic behaviour of good and all embeddings in all cases and we prove that the ratio of good embeddings to all is of the order $Θ (1 / \sqrt{n})$ in all cases, where we provide the exact constants. Furthermore, we show that this ratio is non-decreasing with $S$ in the plane binary case and asymptotically non-decreasing with $S$ in the non-plane binary case and in the planted plane case. Finally, we comment on the case when $S$ is disconnected.

7.4 Other domains

We collaborate with experts in various areas (transport, bio-informatics, e-health, etc.). In this section, we present the results we have obtained in the context of these collaborations.

One important objective of Coati is to use its expertise on graph algorithms and Operations Research to address problems in other scientific domains (transport, bio-informatics, e-health, ed-tech, etc.). During the last years, we have initiated several collaborations with academic and industrial partners in this direction. In this section, we present the last results we have obtained in the context of these collaborations.

7.4.1 Bio-informatics motivated problems

Participants: David Coudert, Emilio Cruciani, Frédéric Havet, Emanuele Natale, Thi Viet Ha Nguyen.

Overlaying a hypergraph with a graph with bounded maximum degree

A major problem in structural biology is the characterization of low resolution structures of macro-molecular assemblies. One subproblem of this very difficult question is to determine the plausible contacts between the subunits (e.g. proteins) of an assembly, given the lists of subunits involved in all the complexes. This problem can be conveniently modelled by graphs and hypergraphs, and we collaborate with Dorian Mazauric (ABS) in order to better understand its computational complexity.

Let $G$ and $H$ be respectively a graph and a hypergraph defined on a same set of vertices, and let $F$ be a fixed graph. We say that $G$ $F$ -overlays a hyperedge $S$ of $H$ if the subgraph of $G$ induced by $S$ contains $F$ as a spanning subgraph, and that $G$ $F$ -overlays $H$ if it $F$ -overlays every hyperedge of $H$ . For a fixed graph $F$ and a fixed integer $k$ , the problem $(Δ \leq k)$ - $F$ -Overlay consists in deciding whether there exists a graph with maximum degree at most $k$ that $F$ -overlays a given hypergraph $H$ . In 87, we prove that for any graph $F$ which is neither complete nor anti-complete, there exists an integer $np (F)$ such that $(Δ \leq k)$ - $F$ -Overlay is NP-complete for all $k \geq np (F)$ .

Graph alignment for brain networks

In collaboration with Rachid Deriche, Samuel Deslauriers-Gauthier and Matteo Frigo (ATHENA), we investigated in 35 the problem of aligning brain atlases. More precisely, the interactions between different brain regions can be modeled as a graph, called connectome, whose nodes correspond to parcels from a predefined brain atlas, and whose edges encode the strength of the axonal connectivity between regions of the atlas that can be estimated via diffusion magnetic resonance imaging (MRI) tractography. In 35, we have provided a novel perspective on the problem of choosing a suitable atlas for structural connectivity studies by assessing how robustly an atlas captures the network topology across different subjects in a homogeneous cohort. We have measured this robustness by assessing the alignability of the connectomes, namely the possibility to retrieve graph matchings that provide highly similar graphs. We have introduced two novel concepts. First, the graph Jaccard index (GJI), a graph similarity measure based on the well-established Jaccard index between sets; the GJI exhibits natural mathematical properties that are not satisfied by previous approaches. Second, we have devised WL-align, a new technique for aligning connectomes obtained by adapting the Weisfeiler-Leman (WL) graph-isomorphism test. We have validated the GJI and WL-align on data from the Human Connectome Project database, inferring a strategy for choosing a suitable parcellation for structural connectivity studies.

7.4.2 Machine learning algorithms

Participants: Arthur Carvalho da Cunha, Emanuele Natale, Chuan Xu.

Hidden learning

In collaboration with Laurent Viennot (GANG, Inria Paris), we investigate in 82 the problem of making a neural network perform some hidden computation whose result can be easily retrieved from the network output. In particular, we consider the following scenario. A user is provided a neural network for a classification task by a company. We further assume that the company has limited access to the user's computation, and can only observe the output of the network when the user evaluates it. The user's input to the network contains some sensible information. We provide a simple and efficient training procedure, called Hidden Learning, that produces two networks such that i) One of the networks solves the original classification task with comparable performance to state of the art solutions of the task; ii) The other network takes as input the output of the first and solves another classification task that retrieves the sensible information with considerable accuracy. Our result might expose important issues from an information security point of view, as for the use of artificial neural networks in sensible applications.

Privacy leakage in federated learning

Federated learning (FL) offers naturally a certain level of privacy, as clients’ data is not collected at a third party. However, maintaining the data locally does not provide itself formal privacy guarantees. An (honest-but-curious) adversary can still infer some sensitive client information just by eavesdropping the exchanged messages (e.g., gradients).

We initiate, in collaboration with Giovanni Neglia (NEO), the study of local model reconstruction attacks for federated learning, where a honest-but-curious adversary eavesdrops the messages exchanged between the client and the server and reconstructs the local model of the client 61. The success of this attack enables better performance of other known attacks, such as the membership attack, attribute inference attacks, etc. We provide analytical guarantees for the success of this attack when training a linear least squares problem with full batch size and arbitrary number of local steps. One heuristic is proposed to generalize the attack to other machine learning problems. Experiments are conducted on logistic regression tasks, showing high reconstruction quality, especially when clients’ datasets are highly heterogeneous (as it is common in federated learning).

In collaboration with Giovanni Neglia (NEO) and Oualid Zari (Intern, Université Côte d'Azur), we study in 62 the membership inference attack, where the adversary can infer whether the client owns a specific data instance. We propose a new passive inference attack that requires much less computation power and memory than existing methods. Our empirical results show that our attack achieves a higher accuracy on CIFAR100 dataset (more than 4 percentage points) with three orders of magnitude less memory space and five orders of magnitude less calculations.

8 Bilateral contracts and grants with industry

8.1 Bilateral contracts with industry

MillionRoads, 2021

Participants: Frédéric Giroire, Nicolas Nisse.

Duration: March 2021 - August 2021
Project title: HumanRoads
Coordinator: Nicolas Nisse
Other partners: SME MillionRoads
Summary: HumanRoads uses a graph database, in the Neo4j environment, to store and structure its data. This database is already large and is regularly enriched with new data. In a previous project with MillionRoads, we have developed methods to optimize queries using algorithms on graphs. In this project, supporting the internship of Imane Houbbane, we have analyzed the data to detect career changes. The objective is to provide students and professionals relevant information for the evolution of their careers.

Orange, 2018-2021

Participants: Frédéric Giroire, Giuseppe Di Lena.

Collaboration with Orange and EP DIANA on the topic of Network Function Virtualization. The activity includes the CIFRE PhD thesis of Giuseppe Di Lena that started his PhD on resilient NFV/SDN environments on April 2018 under the co-supervision of Frédéric Giroire and Thierry Turletti (DIANA).

9 Partnerships and cooperations

9.1 International initiatives

9.1.1 Inria associate team not involved in an IIL or an international program

EfDyNet

Participants: David Coudert, Adrien Gausseran, Frédéric Giroire, Joanna Moulierac.

Title:
Efficient Dynamic Resource Allocation in Networks
Duration:
2019 - 2021
Coordinator:
Frédéric Giroire
Partners:
- Department of Electrical Engineering, Concordia University (Canada)
Summary:
Networks are evolving rapidly in two directions. On the one hand, new network technologies are developed for different layers, and in particular flexible optical technologies (enabling to allocate a fraction of the optical spectrum rather than a fixed wavelength), Software Defined Networks, and Network Function Virtualization. On the other hand, the traffic patterns evolve and become less predictable due to the increase of cloud and mobile traffic. In this context, there are new possibilities and needs for dynamic resource allocations. We will study this problem mainly in two directions: network reconfiguration and the allocation of virtualized resources. The associated team will build on an already fruitful collaboration between COATI and Concordia. The two teams address design and management optimization problems in networks (WDM, wireless, SDN) with complementary tools and expertise.
Web:
team.inria.fr/coati/projects/efdynet/

9.1.2 STIC/MATH/CLIMAT AmSud project

GALOP

Participants: Julien Bensmail, David Coudert, Foivos Fioravantes, Frédéric Giroire, Frédéric Havet, Nicolas Nisse.

Title:
Graphs ALgorithms for Optimization Problems
Duration:
2019 - 2021
Local supervisor:
Nicolas Nisse
Partners:
- Universidade Federal do Ceará
- Universidad Adolfo Ibañez
Inria contact:
Nicolas Nisse
Summary:
This project aims at studying the Computational Complexity of several important problems arising in networks. In particular, we will focus on the computation of metric or structural properties and parameters of large networks. We plan to design efficient exact algorithms for solving these problems or to theoretically prove that such algorithms cannot exist. In the latter case, we will then design approximation algorithms, or prove that none exists. In all cases, we aim at implementing our algorithms and use them on real-world instances such as large road networks or huge social networks.

9.1.3 Participation in other International Programs

DESPROGES

Participants: Julien Bensmail, Foivos Fioravantes, Nicolas Nisse.

Title:
Décompositions arborescentes et problèmes de graphes (DESPROGES).
Coordinator:
Nicolas Nisse
Partner Institution(s):
- Xidian University (Xi’an, Chine).
Duration:
2020 - 2021.
Program:
Partenariats Hubert Curien (PHC) Xu Guangqi.
Summary:
This project aims at studying relationships between tree-decompositions and distinguishing labellings in graphs.

9.2 International research visitors

9.2.1 Visits of international scientists

Pierluigi Crescenzi

Status:
Professor
Institution of origin:
Gran Sasso Science Institute (GSSI), L'Aquila
Country:
Italy
Dates:
October 18-22, 2021
Context of the visit:
collaboration
Mobility program/type of mobility:
research stay

Harmender Gahlawat

Status:
PhD student
Institution of origin:
Indian Statistical Institute Kolkata
Country:
India
Dates:
November 2-5, 2021
Context of the visit:
collaboration
Mobility program/type of mobility:
research stay

9.3 National initiatives

DGA/Inria Brainside, 2019-2023

Participants: Francesco D'Amore, Arthur Carvalho Walraven Da Cunha, Emanuele Natale.

Program:
DGA/Inria
Project acronym:
Brainside
Project title:
Algorithms for simplifying neural networks
Duration:
October 2019 - March 2023
Coordinator:
Emanuele Natale
Other partners:
- Inria Paris, EP GANG
Summary:
The widespread use of neural networks on devices with computationally-low capabilities, demands for lightweight and energy-efficient networks. Despite such need, and despite the strategies employed to prevent overfitting by removing a substantial part of their edges, the question of how to reduce their size in terms of the number of neurons appears largely unexplored. The aim of the project is to investigate algorithmic procedures to reduce the size of neural networks, in order to improve the speed with which they can be evaluated and to shed light on how much information about the computational problem at hand can be encoded within neural networks of small size.

ANR-17-CE22-0016 MultiMod, 2018-2023

Participants: Ali Al Zoobi, David Coudert, Nicolas Nisse, Michel Syska.

Program:
ANR
Project acronym:
MultiMod
Project title:
Scalable routing in Multi Modal transportation networks
Duration:
January 2018 - June 2023
Coordinator:
David Coudert
Other partners:
- Inria Paris, EP GANG
- team CeP, I3S laboratory
- SME Instant-System
- SME Benomad
Summary:
The MultiMod project addresses key algorithmic challenges to enable the fast computation of personalized itineraries in large-scale multi-modal public transportation (PT) networks (bus, tram, metro, bicycle, etc.) combined with dynamic car-pooling. We will use real-time data to propose itineraries with close to real travel-time, and handle user-constraints to propose personalized itineraries. Our main challenge is to overcome the scalability of existing solutions in terms of query processing time and data-structures space requirements, while including unplanned transportation means (car-pooling), real-time data, and personalized user constraints. The combination of car-pooling and PT network will open-up areas with low PT coverage enable faster itineraries and so foster the adoption of car-pooling. We envision that the outcome of this project will dramatically enhanced the mobility and daily life of citizens in urban areas.
Web:
project.inria.fr/multimod/

ANR-19-CE48-0013-01 Digraphs, 2020-2023

Participants: Julien Bensmail, David Coudert, Frédéric Havet, Nicolas Nisse, Stéphane Pérennes.

Program:
ANR
Project acronym:
Digraphs
Project title:
Digraphs
Duration:
January 2020 - December 2023
Coordinator:
Frédéric Havet
Other partners:
- LIRMM, Montpellier
- LIP, Lyon
Summary:
The objectives of the project is to make some advances on digraph theory in order to get a better understanding of important aspects of digraphs and to have more insight on the differences and the similarities between graphs and digraphs. Our methodology is two-fold. On the one hand, we will focus on the tools. Indeed we believe that many proof techniques have been too rarely used or adapted to digraphs and can be developed to obtain many more results.On the second hand, we will consider many results on graphs, find their (possibly many) formulations in terms of digraphs and see if and how they can be extended. Studying such extensions has been occasionally done, but the point here is to do it in a kind of systematic way. Moreover we shall push even further the study by considering classes of digraphs: if a result does not extend to the whole class of digraphs, for which classes does it extend ? if a result extends, can we get better results for some restricted classes of digraphs ?
Web:
project.inria.fr/anrdigraphs/

Défi Inria-Cerema ROAD-AI, 2021-2024

Participants: Christelle Caillouet, David Coudert.

Project acronym:
ROAD-AI
Project title:
Routes et Ouvrages d'Art Diversiformes, Augmentés & intégrés
Duration:
July 2021 - June 2024
Coordinators:
Nathalie Mitton (head, Inria, EP FUN), Christophe Biernacki (vice-head, Inria, EP MODAL), Pierre Marchand (Cerema, DTEC ITM), André Orcési (Cerema, DTEC ITM)
Inria participants:
Inria project-teams ACENTAURI, COATI, FUN, MODAL, STATIFY, MODAL
Other partners:
Cerema
Summary:
Integrated management of infrastructure assets is an approach which aims at reconciling long-term issues with short-term constraints and operational logic. The main objective is to enjoy more sustainable, safer and more resilient transport infrastructure through effective, efficient and responsible management. To achieve this, CEREMA and Inria are joining forces in this Inria Challenge (DEFI) which main goals are to overcome scientific and technical barriers that lead to the asset management of tomorrow for the benefit of road operators: (i) build a “digital twin” of the road and its environment at the scale of a complete network; (ii) define “laws” of pavement behavior; (iii) instrument system-wide bridges and tunnels and use the data in real time; (iv) define methods for strategic planning of investments and maintenance.

9.3.1 GDR Actions

GDR RSD, ongoing (since 2006)

Members of Coati are involved in the working group RESCOM (Réseaux de communications) of GDR RSD, CNRS (gdr-rsd.fr/?page_id=159). In particular, David Coudert is co-chair of this working group since 2017.

We are also involved in the working group "Energy" of GDR RSD (gdr-rsd.fr/?page_id=166). In particular, Frédéric Giroire is co-chair of this working group.

GDR IM, ongoing (since 2006)

Members of Coati are involved in the working group "Graphes" of GDR IM, CNRS. (gtgraphes.labri.fr/). In particular, Frédéric Havet is member of the steering committee.

GDR MADICS, ongoing (since 2017)

Members of Coati are involved in the working group GRAMINEES (GRaph data Mining in Natural, Ecological and Environnemental Sciences) of GDR MADICS (Masses de Données, Informations et Connaissances en Sciences). (www.madics.fr/actions/actions-en-cours/graminees/).

9.4 Regional initiatives

SNIF, 2018-2021

Participants: David Coudert, Frédéric Giroire, Nicolas Nisse, Stéphane Pérennes, Malgorzata Sulkowska, Thibaud Trolliet.

Program:
Innovation project of IDEX UCA $^{JEDI}$ .
Project acronym:
SNIF
Project title:
Scientific Networks and IDEX Funding
Duration:
September 2018 - August 2021
Coordinator:
Patrick Musso
Other partners:
- GREDEG
- SKEMA
- I3S (SigNet)
Summary:
Scientific collaboration networks play a crucial role in modern science. This simple idea underlies a variety of initiatives aiming to promote scientific collaborations between different research teams, universities, countries and disciplines. The recent French IDEX experience is one of them. By fostering competition between universities and granting few of them with a relatively small amount of additional resources (as compared to their global budget), public authorities aim to encourage them to deeply reshape the way academic activities are organized in order to significantly increase the quality of their research, educational programs and innovative activities. The development of new collaboration networks is one of the factors at the heart of this global reorganization. Promoting new international and/or interdisciplinary collaborations is supposed to increase researchers’ productivity and industry partnerships. This project aims to question the validity of this line of thought.

Bourse “Emplois Jeunes Doctorants”, Région SUD PACA, 2018-2021

Participants: Ali Al Zoobi, David Coudert, Nicolas Nisse.

Program:
Bourse “Emplois Jeunes Doctorants”, Région SUD PACA
Project title:
Algorithmes pour le transport collectif à la demande dynamique en zone urbaine
Duration:
October 2018 - September 2021
Coordinator:
David Coudert
Other partners:
Instant-System
Summary:
We aim at designing algorithms that will eventually make it possible to consistently deploy a real-time on-demand public transport service in urban areas by integrating it with the regular public transport offer. To reach this goal, we must design a set of algorithms to respond very quickly (less than a second) to a user's request, made from their smartphone. This raises many difficult questions related to the dial-a-ride-problem.

10 Dissemination

10.1 Promoting scientific activities

10.1.1 Scientific events: organisation

General chair, scientific chair

David Coudert and Emanuele Natale.
- SEA'21: 19th Symposium on Experimental Algorithms, Nice (online), France, June 7-9, 2021 (see sea2021.i3s.unice.fr). Proceedings 64

10.1.2 Scientific events: selection

Chair of conference program committees

David Coudert and Emanuele Natale.
- SEA'21: 19th Symposium on Experimental Algorithms, Nice (online), France, June 7-9, 2021 (sea2021.i3s.unice.fr)

Member of the conference program committees

Ramon Aparicio :
- ACM MMSys'21: International Conference on Multimedia Systems, Istanbul, Turkey, September 28 - October 1st, 2021;
- IEEE Globecom'21: IEEE Global Communications Conference, Madrid, Spain, December 7-11, 2021.
Christelle Caillouet :
- CoRes'21: 6ème Rencontres Francophones sur la Conception de Protocoles, l’Evaluation de Performance et l’EXpérimentation des Réseaux de Communication, La Rochelle, September 20-24, 2021.
David Coudert :
- ALGOCLOUD'21: International Symposium on Algorithmic Aspects of Cloud Computing, online, September 6-7, 2021;
- IEEE ICC'21: IEEE International Conference on Communications, Virtual Conference, June 14-23, 2021;
- IEEE Globecom'21: IEEE Global Communications Conference, Madrid, Spain, December 7-11, 2021;
- ONDM'21: 25th Conference on Optical Network Design and Management, online, June 28 - July 1st, 2021.
Frédéric Havet :
- LAGOS 2021: XI Latin and American Algorithms, Graphs and Optimization, Sao Paulo, Brazil, May 17-21, 2021;
- JGA 2021: Journées Graphes et Algorithmes, Montpellier (on-line), November 15-19, 2021.
Joanna Moulierac :
- CoRes'21: 6ème Rencontres Francophones sur la Conception de Protocoles, l’Evaluation de Performance et l’EXpérimentation des Réseaux de Communication, La Rochelle, September 20-24, 2021.
Emanuele Natale
- AAMAS'21: 20th International Conference on Autonomous Agents and Multiagent Systems, virtual event, May 3-7, 2021;
- Euro-Par'21: 27th International European Conference on Parallel and Distributed Computing, virtual event, August 30 - September 3, 2021.
Nicolas Nisse :
- AlgoTel'21: 23es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, La Rochelle, September 20-24, 2021.

Reviewer

Members of COATI have reviewed numerous manuscripts submitted to national and international conferences, including:

AAAI'22; AAMAS'21; ACM MMSys; ALGOCLOUD'21; ALGOSENSORS'21; AlgoTel'21; CoRes'21; Euro-Par'21; IEEE ICC'21; IEEE Globecom'21; LAGOS'21; MFCS'21; NeurIPS'21; ONDM'21; PODC'21; SEA'21; STACS'22; WADS'21.

10.1.3 Journal

Member of the editorial boards

Ramon Aparicio-Pardo :
- Guest Editor: Special Issue on Optical Network Automation for MDPI Sensors (ISSN 1424-8220).
Jean-Claude Bermond :
- Computer Science Reviews (Elsevier);
- Discrete Applied Mathematics (Elsevier);
- Discrete Mathematics (Elsevier);
- Discrete Mathematics, Algorithms and Applications (World Scientific);
- Journal of Graph Theory (Wiley);
- Advisory board of Journal of Interconnection Networks (World Scientific);
- Networks (Wiley);
- Parallel Processing Letters (World Scientific);
- the SIAM book series on Discrete Mathematics (SIAM).
Alexandre Caminada :
- IEEE Transactions on Mobile Computing (IEEE);
- IEEE Transactions on Vehicular Technology (IEEE);
- Journal of Traffic and Transportation Engineering (Elsevier);
- Sensors — Open Access Journal (MDPI);
- Soft Computing (Springer).
David Coudert :
- Discrete Applied Mathematics (Elsevier);
- Networks (Wiley).
Frédéric Giroire :
- Journal of Interconnection Networks (World Scientific);
- Telecom (MDPI).
Frédéric Havet
- Discrete Mathematics and Theoretical Computer Science (DMTCS).
Emanuele Natale
- The WikiJournal of Science (Wikimedia Foundation).

Reviewer - reviewing activities

Members of COATI have reviewed numerous manuscripts submitted to international journals, including:

ACM Journal of Experimental Algorithmics; Combinatorics, Probability and Computing; Computer Networks (COMNET); Computers & Operations Research (COR); Discrete Mathematics; Discrete Applied Mathematics (DAM); Discrete Mathematics and Theoretical Computer Sciences (DMTCS); European Journal of Operational Research (EJOR); IEEE Internet of Things Journal; IEEE Transactions on Mobile Computing (TOMC); IEEE Transactions on Network and Service Management; IEEE Transactions on Network Science and Engineering; INFORMS Journal on Computing; Journal of Combinatorial Theory Ser. B; MDPI Future Internet; MDPI Sensors; Networks (Wiley); SIAM Journal of Discrete Mathematics (SIDMA); Springer Photonic Network Communications; The Computer Journal; Theoretical Computer Science (TCS).

10.1.4 Invited talks

Julien Bensmail :
- An introduction to the 1-2-3 Conjecture (and related problems). Invited speaker at “42èmes Journées Franciliennes de Recherche Opérationnelle” (JFRO), online, September 2021;
- A proof of the Multiplicative 1-2-3 Conjecture. Séminaire du groupe de travail Graphes et Optimisation, LaBRI, Université de Bordeaux, September 2021.
David Coudert :
- On the Flinders Hamiltonian Cycle Problem Challenge. Seminar of the Romanian Young Academy (RYA), online, November 18, 2021.
Francesco d'Amore :
- Search via Parallel Lévy Walks on $ℤ^{2}$ , online seminar at Dipartimento di Logica ed Informatica Teorica, Università Roma Tre (IT), online, April 2021.
Hicham Lesfari :
- Graph learning for networking, meeting of the Scientific and Pedagogical Advisory Board (SPAB) of EUR DS4H, Université Nice Côte d'Azur, July 28-29, 2021
Nicolas Nisse :
- Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation. Graph Searching in Canada (GRASCAN), August 5, 2021 and Seminar of the Romanian Young Academy (RYA), online, November 4, 2021.
Thi Viet Ha Nguyen
- Graph problems motivated by resolution models of large protein assemblies. seminar of the ALGCO team, LIRMM Montpellier, October, 2021.

10.1.5 Leadership within the scientific community

David Coudert :
- Co-chair of Pôle RESCOM of GDR RSD of CNRS since 2017 and member of the steering committee since 2005.
Frédéric Giroire :
- Member of the steering committee of GT Energy of the GDR RSD of CNRS.
Frédéric Havet :
- Member of the steering committee of GT Graphes of the GDR IM of CNRS since 2005;
- President of the PhD prize committee ; Graphes "Charles Delorme".

10.1.6 Scientific expertise

Julien Bensmail :
- External reviewer for the OPUS-21 program by the National Science Center (NSC) of Poland.
Jean-Claude Bermond :
- Expert for DRTT-MESR Crédit impôt recherche (CIR et agréments).
David Coudert :
- Expert for ANR and ANRT;
- External reviewer for the Central Research Development Fund of the University of Bremen.
Frédéric Giroire :
- Member of the expert committee of the MESRI-BMBF German-French Joint Call For Proposals on “Artificial Intelligence” ;
- External reviewer for the European CHIST-ERA Call 2020;
- Reviewer for the Inria associated team process.
Frédéric Havet :
- Expert for ANR and FNRS (Belgium).
Emanuele Natale :
- Grant reviewer for the National Science Center of Poland, SONATA-16 call.
Nicolas Nisse :
- Expert for European Science Foundation;
- Natural Sciences and Engineering Research Council of Canada;
- National Research and Development Agency, ANID, Chile.
Michel Syska :
- Expert for DRTT-MESR Crédit impôt recherche (CIR et agréments).

10.1.7 Research administration

Ramon Aparicio:
- Principal investigator of ARTIC project (ARTificial Intelligence-based Cloud network control), 220 k€ over 42 months funded by ANR JCJC 2019, March 2020 - Sept. 2023.
Jean-Claude Bermond
- Responsible for the cooperation between Inria and Greece.
Christelle Caillouet
- Elected member of Conseil de Laboratoire I3S since 2017;
- Member of selection committee MCF27 749, Université Côte d'Azur, 2021;
- Member of selection committee MCF27 4270, INSA Lyon, 2021.
Alexandre Caminada
- Member of the executive board of the Sophia Interdisciplinary Institute of Artificial Intelligence started in 2019;
- Manager of the research committee for the Polytech network national academic Foundation.
David Coudert :
- Nominated member for Inria at the board of doctoral school STIC, since September 2017;
- Head (since December 2019) and member (since 2009) of the “Comité de Suivi Doctoral” of Inria;
- Nominated member for Inria at the steering committee of Academy 1 RISE (Networks, Information, Digital Society) of UCA $^{JEDI}$ since February 2018;
- Nominated member for Inria at the steering committee of EUR DS4H since February 2018;
- Nominated member for Inria at the steering committee of Labex UCN@Sophia since February 2018;
- Member of the steering committee of seminar Forum Numerica of Academy 1 RISE of UCA $^{JEDI}$ since 2018;
- Member of the “Bureau du comité des équipe-projets” of Inria research center Sophia Antipolis - Méditerranée since 2018;
- Member of selection committee MCF27 749, Université Côte d'Azur, 2021.
Frédéric Giroire :
- In charge of the internships of stream UbiNet of Master 2 IFI, Université Côte d'Azur.
Frédéric Havet
- Head of COMRED team of I3S laboratory.
Emanuele Natale :
- Member of selection committee MCF27 749, Université Côte d'Azur, 2021.
Nicolas Nisse :
- Elected member for the "Comité de centre", Inria Sophia Antipolis - Méditerranée, since 2017;
- Elected member for Inria at the CoSP of EUR DS4H since October 2020;
- Member of the CoSP Terra Numerica, since 2020.
Michel Syska
- Nominated deputy director of the computing science department of Université Côte d'Azur (Département Disciplinaire Informatique) : March 2020 - March 2021.

10.2 Teaching - Supervision - Juries

10.2.1 Teaching Responsibilities

Julien Bensmail :
- Head of the Licence Professionnelle “Managements des Processus Logistiques” (MPL) of Université Côte d'Azur, since September 2019.
Alexandre Caminada
- Head of the graduate school of engineering Polytech Nice Sophia (1500 master grade students, 100 faculty members, 50 staffs);
- Member of the executive board of the Polytech network, national network of public graduate school of engineering;
- Member of the executive board of Université Côte d'Azur.
Joanna Moulierac :
- “Directrice d'études” for the 1st-year students of “Département Informatique” of IUT Nice Côte d'Azur (since September 2017);
- Head of the “Conseil de Département Informatique” of IUT Nice Côte d'Azur (since September 2017).
Michel Syska :
- Vice Head of the Bachelor’s degree in Artificial Intelligence (Licence Sciences et Technologies parcours IA), of Université Côte d'Azur;
- Head of "Campus des Métiers et des Qualifications - défi du numérique", Université Côte d'Azur, Rectorat et Région PACA (since May 2021).

10.2.2 Teaching

Members of Coati have taught for more that 1650 hours (ETD) this year:

DUT: Julien Bensmail, Recherche opérationnelle, 90h ETD, Level L2, Département QLIO of IUT, Université Côte d'Azur, France;
DUT: Julien Bensmail, Systèmes de gestion de bases de données, 70h ETD, Level L2, Département QLIO of IUT, Université Côte d'Azur, France;
DUT: Christelle Caillouet, Object Oriented Programming, 150h ETD, Level L1, IUT, Université Côte d'Azur, France;
DUT: Christelle Caillouet, Introduction to Networks, 21h ETD, Level L1, IUT, Université Côte d'Azur, France;
DUT: Christelle Caillouet, Algorithmics, 21h ETD, Level L2, IUT, Université Côte d'Azur, France;
DUT: Thomas Dissaux, Introduction aux Bases de données et SQL, 30h ETD, Level L1, Département Informatique of IUT, Université Côte d'Azur, France;
DUT: Thomas Dissaux, Bases de la Conception Orientée Objet, 64h ETD, Level L1, Département Informatique of IUT, Université Côte d'Azur, France;
DUT: Foivos Fioravantes, Bases de Données, 32h ETD, Level L1, Département Informatique of IUT, Université Côte d'Azur, France;
DUT: Foivos Fioravantes, Conception Orientée Objet, 32h ETD, Level L1, Département Informatique of IUT, Université Côte d'Azur, France;
DUT: Adrien Gausseran, Introduction à l'algorithmique et à la programmation, 10h ETD, Level L1, IUT, Université Côte d'Azur, France;
DUT: Adrien Gausseran, Architecture des réseaux, 38h ETD, Level L1, IUT, Université Côte d'Azur, France;
DUT: Adrien Gausseran, Compléments d'algorithmique, 20h ETD, Level L2, IUT, Université Côte d'Azur, France;
DUT: Luc Hogie, Distributed programming, 28h ETD, Level L2, IUT, Université Côte d'Azur, France;
DUT: Hicham Lesfari, Réseaux d'opérateurs et réseaux d'accès, 48h ETD, Level L2, IUT, Université Côte d'Azur, France;
DUT: Joanna Moulierac, Introduction à l'algorithmique, 30h ETD, Level L1, IUT, Université Côte d'Azur, France;
DUT: Joanna Moulierac, Introduction aux Réseaux, 56h ETD, Level L1, IUT, Université Côte d'Azur, France;
DUT: Joanna Moulierac, Réseaux avancés, 30h ETD, Level L2, IUT, Université Côte d'Azur, France;
DUT: Thi Viet Ha Nguyen, Algorithmique, 24h ETD, Level L1, Département QLIO of IUT, Université Côte d'Azur, France;
DUT: Thibaud Trolliet, Introduction aux bases de données, 64h ETD, Level L1, IUT, Université Côte d'Azur, France;
DUT: Michel Syska, Data Structures and Algorithms, 44h ETD, Level L2, IUT, Université Côte d'Azur, France;
DUT: Michel Syska, Introduction to Artificial Intelligence, 48h ETD, Level L2, IUT, Université Côte d'Azur, France;
DUT: Michel Syska, Algorithmics, 53h ETD, Level L2, IUT, Université Côte d'Azur, France;
DUT: Michel Syska, Distributed programming, 87h ETD, Level L2, IUT, Université Côte d'Azur, France;
DUT: Luc Hogie, Distributed programming, 24h ETD, Level L2, IUT, Université Côte d'Azur, France;
MPSI: Nicolas Nisse, Option informatique, MPSI, 24h ETD, classe préparatoire MPSI, Lycée International de Valbonne, France;
Licence: Redha Abderrahmane Alliche, Systèmes et Réseaux, 24h ETD, Level L3, Polytech Nice-Sophia, France;
Licence: Ali Al Zoobi, Programmation et structures en C, 24h ETD, Level L2, Faculté des sciences, Université Côte D'Azur, France;
Licence: Julien Bensmail, Sécurité des échanges de données inter-entreprises, 30h ETD, Level L3, LP MPL of IUT, Université Côte d'Azur, France;
Licence: Michel Syska, Networks, 31h ETD, Level L3, MIAGE - Université Côte d’Azur, France;
Licence: Luc Hogie, Programmation et Conception Orientée Objet, 24h ETD, Level L3, IA - Université Côte d’Azur, France;
License: Chuan Xu, Programmation fonctionnelle, 36h ETD, Level L3, Université Côte d’Azur, France;
License: Chuan Xu, Python pour l'IA, 30h ETD, Level L3, Université Côte d’Azur, France;
Master: Christelle Caillouet, Data Mining for Networks, 9h ETD, M2 Ubinet, Université Côte d'Azur, France;
Master: Alexandre Caminada, Radio location systems, 20h ETD, Master 2 (in english), Polytech Nice Sophia, France;
Master: Alexandre Caminada, Artificial intelligence, 40h ETD, Master 2 (in english), Polytech Nice Sophia, France;
Master: Alexandre Caminada, Master grade student's internship supervision and assesment, 10h ETD, Master 2, Polytech Nice Sophia, France;
Master: David Coudert, Algorithms for Telecoms, 36h ETD, M2 Ubinet, Université Nice Sophia Antipolis, France;
Master: Frédéric Giroire, Graph Algorithms, 18h ETD, Master 2, International Track Ubinet, Université Côte d'Azur, France;
Master: Frédéric Giroire, Machine learning for networks, 24h ETD, Master 2, International Track Ubinet, Université Côte d'Azur, France;
Master: Frédéric Giroire, ICT and Environment, Green algorithm design, 4.5h ETD, Master 2, minor, Université Côte d'Azur, France;
Master: Nicolas Nisse, Graphs, 36h ETD, M1 Informatique et Interaction, Université Côte d'Azur, France;
Master: Nicolas Nisse, Algorithms for Telecoms, 15h ETD, M2 Ubinet, Université Côte d'Azur, France;
Master: Nicolas Nisse, Advanced Graphs, 36h ETD, M2 Informatique et Interaction, Université Côte d'Azur, France.

10.2.3 Supervision

PhD thesis

PhD in progress: Redha Abderrahmane Alliche, Artificial Intelligence-based cloud network control, since October 2020. Co-supervisors: Ramon Aparicio and Lucile Sassatelli;
PhD in progress: Arthur Carvalho Walraven Da Cunha, Algorithmic Principles for Artificial Neural Network Compression, since October 2020. Supervisor: Emanuele Natale;
PhD in progress: Francesco d'Amore, Dynamics for multi-agent system coordination in noisy and stochastic environments, since October 2019. Co-supervisors: Emanuele Natale and Nicolas Nisse;
PhD in progress: Thomas Dissaux, Graph decompositions and treelength, since October 2020. Supervisor: Nicolas Nisse;
PhD in progress: Foivos Fioravantes, Distinguishing labellings of graphs, since October 2019. Co-supervisors: Julien Bensmail and Nicolas Nisse;
PhD in progress: Igor Dias da Silva, Optimization of UAVs deployment and coordination for exploration and monitoring applications, since October 2020. Co-supervisors: Christelle Caillouet and David Coudert;
PhD in progress: Hicham Lesfari, Machine learning for dynamic network resource allocation, since October 2019. Supervisor: Frédéric Giroire;
PhD in progress: Zhejiayu Ma, Learning problem for the diffusion of multimedia contents, since October 2018. Co-Supervisors: Guillaume Urvoy-Keller, Frédéric Giroire, Soufiane Rouiba (Easybroadcast, Nantes). CIFRE grant with Easybroadcast;
PhD in progress: Lucas Picassari-Arrieta , digraphs coloring, since October 2021. Supervisor: Frédéric Havet;
PhD: Ali Al Zoobi, Algorithms for shared on demand public transportation system in the city, Université Côte d'Azur, November 25, 2021. Co-supervisors: David Coudert and Nicolas Nisse;
PhD: Giuseppe Di Lena, Resilience of virtualized networks 65, March 22, 2021. Co-supervisors: Thierry Turletti (DIANA), Chidung Lac (Orange Labs Lannion) and Frédéric Giroire. CIFRE grant with Orange;
PhD: Adrien Gausseran, Optimization Algorithms for Network Slicing for 5G 66, November 9, 2021. Supervisors: Joanna Moulierac and Nicolas Nisse;
PhD: Thi Viet Ha Nguyen, Graph Algorithms techniques for (low and high) resolution model of large protein assemblies 67, December 13, 2021. Co-supervisors: Frédéric Havet and Dorian Mazauric (ABS);
PhD: Thibaud Trolliet, Exploring Trust on Twitter 68, June 25, 2021. Co-supervisors: Arnaud Legout (DIANA) and Frédéric Giroire.

Internships

DUT: Fedi Ghalloussi, Réalisation d’une interface web pour l’intergiciel Idawi, Inria, from May 2021 until Jul 2021. Supervisor: Luc Hogie;
Licence: Hugo Boulier, Affectation de longueurs d'ondes dans les réseaux optiques sans filtres, ENS Rennes, France, from May 15 until July 5 2021. Supervisor: David Coudert, Frédéric Havet and François Pirot;
Licence: Cyprien Michel-Deletie, Null Processes for Computational Neuroscience, L3 ENS Lyon, May 31 till July 09, 2021. Supervisors: Emanuele Natale, Matteo Frigo (ATHENA), Samuel Deslauriers-Gauthier (ATHENA);
Licence: Nacim Oijid, The Maker-Breaker Largest Connected Subgraph Game, L3 ENS Lyon, from Apr 2021 until Jun 2021. Supervisor: Nicolas Nisse;
Licence: Juliette Schabanel, Dichromatic number of surfaces, L3 ENS Paris, from Jun 2021 until Jul 2021. Supervisors: Frédéric Havet and François Pirot;
Master 1 (PFE): Khadidiatou Dieye, Web dev/ergonomics : Conception and implementation of a Web graph library/plaform, Master 1 MIAGE, Université Côte d'Azur, France, from November 2021 until December 2021. Supervisor: Luc Hogie;
Master 1: Pierre Pebereau Calcul exact de la pathlength par branch-and-bound, 2nd year Télécom Paris, from July 5 until August 31, 2021. Supervisors: David Coudert and Nicolas Nisse;
Master 2 (PFE): Maria Darido, Data acquisition and collection in harsh environment, Master 2 IFI, international track Ubinet, Université Côte d'Azur, France, from November 2021 until December 2021. Supervisors: Christelle Caillouet and David Coudert;
Master 2 (PFE): Tiago Da Silva Barros, Network simulator for reinforcement learning, Master 2 IFI, international track Ubinet, Université Côte d'Azur, France, from November 2021 until December 2021. Supervisors: Ramon Aparicio-Pardo;
Master 2 (PFE): Barbara Da Silva Oliveira, Quantum Entanglement Routing, Master 2 IFI, international track Ubinet, Université Côte d'Azur, France, from November 2021 until December 2021. Supervisors: Ramon Aparicio-Pardo;
Master 2 (PFE): Hassan El Chokraallah, Using semantic graph clustering to explore study and career paths with the goal to help student and professional counselling, Master 2 IFI, international track Ubinet, Université Côte d'Azur, France, from November 2021 until December 2021. Supervisors: Frédéric Giroire and Nicolas Nisse;
Master 2 (PFE): Mohamed Jadar, Federated Learning On Heterogeneous Systems, Master 2 IFI, international track Ubinet, Université Côte d'Azur, France, from November 2021 until December 2021. Supervisors: Chuan Xu;
Master 2 (PFE): Mohamed Lahsini, Deep Reinforcement Learning for Video caching, aster 2 IFI, international track Ubinet, Université Côte d'Azur, France, from November 2021 until December 2021. Supervisors: Ramon Aparicio-Pardo;
Master 2 (PFE): Leonardo Serilli, Evolution over time of the structure of social graphs: Clustering, Master 2 IFI, international track Ubinet, Université Côte d'Azur, France, from November 2021 until December 2021. Supervisors: Frédéric Giroire, Nicolas Nisse, Małgorzata Sulkowska;
Master 2: Gregory Hoareau, Programming a firendly interface for playing to cops and robber games, Polytech’Nice, 5th year, speciality HCI, Université Côte d'Azur, France, from Mar 2021 until Sep 2021. Supervisors: Frédéric Havet, Dorian Mazauric, Nicolas Nisse and Michel Syska;
Master 2: Imane Houbbane, Explore study and career paths with the goal to help student and professional counselling, Master 2 IFI, international track Ubinet, Université Côte d'Azur, France, from March 2021 until August 2021. Supervisors: Frédéric Giroire and Nicolas Nisse;
Master 2: Kostiantyn Ohulchanskyi, Random preferential attachment hypergraph with vertex deactivation, Master 2 IFI, international track Ubinet, Université Côte d'Azur, France, from March 2021 until August 2021. Supervisors: Frédéric Giroire, Nicolas Nisse, Małgorzata Sulkowska, Thibaud Trolliet;
Master 2: Marcello Politi, A computational study of iterative pruning algorithms, University of Rome 2 "Tor Vergata", Rome, Italy. From March to July 2021. Supervisor: Emanuele Natale;
Master 2: Sofiia Shelest, Evolution over time of the structure of social graphs, Master 2 IFI, international track Ubinet, Université Côte d'Azur, France, from March 2021 until August 2021. Supervisors: Frédéric Giroire, Nicolas Nisse, Małgorzata Sulkowska, Thibaud Trolliet.

10.2.4 Juries

Jean-Claude Bermond :
- invited member for the HDR of Dorian Mazauric, Université Côte d'Azur, November 5, 2021.
Christelle Caillouet :
- Member of the Comité de Suivi individuel of the PhD thesis of Masoud Taghavian, IMT Atlantique, June 14, 2021;
- Member of the PhD committee of Takwa Attia, Optimization and experimental characteriza- tion of Low Power Wide Area Networks, LIG, Université de Grenoble Alpes, December 15, 2021.
David Coudert :
- Member of the PhD committee of Antonin Lentz, Calcul de plus courts chemins multicritères et problèmes géométriques connexes, LaBRI, Bordeaux, France, July 5, 2021;
- Member of the Comité de Suivi individuel of the PhD thesis of Federico Brunero, Eurecom, Sophia Antipolis, January 15 2021 and September 30, 2021;
- Referee and member of the PhD committee of Samuel Masseport, Consensus blockchain: incitation des utilisateurs à la participation et à la loyauté, LIRMM, Université de Montpellier, October 12, 2021;
- President of the PhD committee of Nicolas Isoart, Le problème du voyageur de commerce en programmation par contraintes, I3S, Université Côte d'Azur, Sophia Antipolis, France, November 19, 2021.
Frédéric Havet :
- Member of PhD committee of Florian Hoersch, Université Grenoble Alpes, September 27, 2021;
- Member of PhD committee of Valentin Bartier, Université Grenoble Alpes, November 29, 2021.
Joanna Moulierac :
- Member of the PhD committee of Sihem Bakri, Vers l’application du découpage du réseau en 5G, Eurecom, Sophia Antipolis, France, January 28, 2021.
Michel Syska :
- Member of the jury of the CAPES (certificate of aptitude for secondary school teachers) Numérique et Sciences Informatiques, written tests and oral tests at Université Claude Bernard, Lyon 1, France, June 23-30, 2021.

10.3 Popularization

10.3.1 Internal or external Inria responsibilities

Frédéric Havet is head of the “Comité Scientifique, Pédagogique et Technique” and member of the executive board of Terra Numerica (see terra-numerica.org/);
Frédéric Havet is vice-president and member of the scientific committee of the association Institut Esope 21 (esope21.fr/). In particular, he is in charge of the organization of the “Carrefour des Sciences” at Vinon-sur-Verdon secondary school;
Nicolas Nisse is head of Galejade projet (Graphes et ALgorithmes : Ensemble de Jeux À Destination des Ecoliers... (mais pas que)). See galejade.inria.fr/.

10.3.2 Articles and contents

Many members of Coati are importantly involved in Terra Numerica (see terra-numerica.org/) and participate to the creation of several popularization systems of science popularization : games, activities, on-line resources, ...

We have published a popularization article on optimization problems in telecommunications networks in a special issue on operations research of the science popularization journal Tangente 29.

10.3.3 Education

Frédéric Havet : Formation de professeurs de collège à la MIA. February 17, 2021;
Frédéric Havet : Formation de médiateur à la Maison de l'Intelligence Artificielle, April 06, 2021;
Frédéric Havet and Nicolas Nisse : Formation de médiateur à la Maison de l'Intelligence Artificielle, May 27, 2021;
Frédéric Havet and Nicolas Nisse : Formation de professeurs des écoles et de collège à la méthode Galejade. November 19, 2021;
Hicham Lesfari is scientific mediator at Maison de l’Intelligence Artificielle and Terra Numerica.

10.3.4 Interventions

Ali Al Zoobi:
- Fête de la science, “machine learning with dogs and cats”, Villeneuve Loubet, October 16-17, 2021;
- Presenting “games on graphs” at the Maison de l'intelligence Artificelle (MIA), Sophia Antipolis, November 18-19, 2021.
Frédéric Giroire :
- Participation to a Projet pédagogique sur éthique de l’information et des données (Collège Sidney Bechet, Antibes - Terra Numerica). 3 interventions on recommendation algorithms in social networks in the collège Bechet and in the Maison de l'Intelligence Articificielle Sophia, April-May, 2021.
Frédéric Havet :
- Organization of “Carrefour des sciences”, Institut Esope 21 at Collège de Vinon-sur-Verdon, October 4-8, 2021;
- A dozen of conferences at “Carrefour des sciences”, Collège de Vinon-sur-Verdon, October 4-8, 2021;
- Conference grand public “Vers l'infini et au delà” , Rians, Var, March 26, 2021;
- Conference grand public “Les algorithmes: des origines à l'I.A.” Brignoles, Var, October 6, 2021;
- Conference “Maths et magie” and “L'élégance des mathématiques”, Collège Henri Nans, Aups, October 22, 2021.
Hicham Lesfari
- Fête de la science, Nice, October 10, 2021.
Nicolas Nisse :
- Fête de la science, Villeneuve Loubet, October 3, 2021; Nice, October 10, 2021; Antibes-Juan les Pins, October 16-17, 2021;
- Musée des arts concrets, Mouans Sartoux, October 5 and 8, 2021.

11 Scientific production

11.1 Major publications

1 articleD.Deepesh Agarwal, C.Christelle Caillouet, D.David Coudert and F.Frédéric Cazals. Unveiling Contacts within Macro-molecular assemblies by solving Minimum Weight Connectivity Inference Problems.Molecular and Cellular Proteomics14April 2015, 2274-2284
HAL DOI
2 inproceedingsL.Luca Becchetti, A.Andrea Clementi, E.Emanuele Natale, F.Francesco Pasquale and L.Luca Trevisan. Finding a Bounded-Degree Expander Inside a Dense One.Proceedings of the thirty-first Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Salt Lake City, United StatesJanuary 2020
HAL
3 articleJ.Julien Bensmail, A.Ararat Harutyunyan, T.-N.Tien-Nam Le and S.Stéphan Thomassé. Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture.Combinatorica392April 2019, 239-263
HAL DOI
4 articleC.Christelle Caillouet, F.Frédéric Giroire and T.Tahiry Razafindralambo. Efficient Data Collection and Tracking with Flying Drones.Ad Hoc Networks89C2019, 35-46
HAL DOI
5 articleN.Nathann Cohen, F.Frédéric Havet, W.William Lochet and N.Nicolas Nisse. Subdivisions of oriented cycles in digraphs with large chromatic number.Journal of Graph Theory894April 2018, 439-456
HAL DOI
6 articleD.David Coudert, G.Guillaume Ducoffe and N.Nicolas Nisse. To Approximate Treewidth, Use Treelength!SIAM Journal on Discrete Mathematics3032016, 13
HAL DOI
7 articleD.David Coudert, G.Guillaume Ducoffe and A.Alexandru Popa. P-FPT algorithms for bounded clique-width graphs.ACM Transactions on Algorithms153June 2019, 1-57
HAL DOI
8 inproceedingsE.Emilio Cruciani, E.Emanuele Natale and G.Giacomo Scornavacca. Distributed Community Detection via Metastability of the 2-Choices Dynamics.AAAI 2019 - 33th AAAI Conference Association for the Advancement of Artificial IntelligenceHonolulu, United StatesJanuary 2019
HAL
9 articleF.François Dross and F.Frédéric Havet. On the Unavoidability of Oriented Trees.Electronic Notes in Theoretical Computer Science346August 2019, 425-436
HAL DOI
10 articleF.Frédéric Giroire, F.Frédéric Havet and J.Joanna Moulierac. On the Complexity of Compressing Two Dimensional Routing Tables with Order.Algorithmica801January 2018, 209-233
HAL DOI
11 inproceedingsM.Martin Heusse, T.Takwa Attia, C.Christelle Caillouet, F.Franck Rousseau and A.Andrzej Duda. Capacity of a LoRaWAN Cell.Proceedings of the 23rd International ACM Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM 2020)MSWiM '20alicante, SpainAssociation for Computing MachineryNovember 2020, 131--140
HAL DOI
12 patentL.Luc Hogie, M.Michel Syska and N.Nicolas Chleq. BigGraphs: distributed graph computing.IDDN.FR.001.410005.000.S.P.2015.000.31235FranceSeptember 2016
HAL
13 articleW.William Lochet. Immersion of transitive tournaments in digraphs with large minimum outdegree.Journal of Combinatorial Theory, Series BMay 2018, 4
HAL DOI
14 articleM.Myriana Rifai, N.Nicolas Huin, C.Christelle Caillouet, F.Frédéric Giroire, J.Joanna Moulierac, D.Dino Lopez Pacheco and G.Guillaume Urvoy-Keller. Minnie : An SDN world with few compressed forwarding rules.Computer Networks121July 2017, 185-207
HAL DOI
15 inproceedingsA.Andrea Tomassilli, F.Frédéric Giroire, N.Nicolas Huin and S.Stéphane Pérennes. Provably Efficient Algorithms for Placement of Service Function Chains with Ordering Constraints.IEEE INFOCOM 2018 - IEEE Conference on Computer CommunicationsHonolulu, United StatesIEEEApril 2018
HAL DOI

11.2 Publications of the year

International journals

16 articleA.Alan Arroyo, J.Julien Bensmail and B. R.Bruce R. Richter. Extending Drawings of Graphs to Arrangements of Pseudolines.Journal of Computational Geometry1222021, 3-24
HAL DOI back to text
17 articleJ.Julien Bensmail, S.Sandip Das, S.Soumen Nandi, S.Soumyajit Paul, T.Théo Pierron, S.Sagnik Sen and E.Eric Sopena. Pushable chromatic number of graphs with degree constraints.Discrete Mathematics34412021, 112151
HAL DOI back to text
18 articleJ.Julien Bensmail, S.Sandip Das, S.Soumen Nandi, T.Théo Pierron, S.Sagnik Sen and E.Eric Sopena. On the signed chromatic number of some classes of graphs.Discrete Mathematics3452022, 112664
HAL DOI back to text
19 articleJ.Julien Bensmail, F.Foivos Fioravantes, F.Fionn Mc Inerney and N.Nicolas Nisse. Further Results on an Equitable 1-2-3 Conjecture.Discrete Applied Mathematics2972021, 1-20
HAL DOI back to text
20 articleJ.Julien Bensmail, F.Foivos Fioravantes and F.Fionn Mc Inerney. On the Role of 3s for the 1-2-3 Conjecture.Theoretical Computer Science8922021, 238-257
HAL DOI back to text
21 articleJ.Julien Bensmail, F.Foivos Fioravantes and N.Nicolas Nisse. On Proper Labellings of Graphs with Minimum Label Sum.Algorithmica2021
HAL back to text
22 articleJ.Julien Bensmail and F.Foivos Fioravantes. On BMRN*-colouring of planar digraphs.Discrete Mathematics and Theoretical Computer Science231February 2021, #4
HAL DOI back to text
23 articleJ.Julien Bensmail, H.Hervé Hocquard, D.Dimitri Lajou and E.Eric Sopena. Further Evidence Towards the Multiplicative 1-2-3 Conjecture.Discrete Applied Mathematics3072022, 135-144
HAL DOI back to text
24 articleJ.Julien Bensmail, B.Bi Li and B.Binlong Li. An injective version of the 1-2-3 Conjecture.Graphs and Combinatorics372021, 281-311
HAL DOI back to text
25 articleJ.Julien Bensmail, B.Bi Li, B.Binlong Li and N.Nicolas Nisse. On Minimizing the Maximum Color for the 1-2-3 Conjecture.Discrete Applied Mathematics2892021, 32-51
HAL DOI back to text
26 articleJ.Julien Bensmail, F.Fionn Mc Inerney and K.Kasper Lyngsie. On {a,b}-edge-weightings of bipartite graphs with odd a,b.Discussiones Mathematicae Graph Theory4212022, 159-185
HAL DOI back to text
27 articleJ.Julien Bensmail and F.Fionn Mc Inerney. On Generalisations of the AVD Conjecture to Digraphs.Graphs and Combinatorics372021, 545-558
HAL DOI back to text
28 articleJ.Julien Bensmail. On a graph labelling conjecture involving coloured labels.Discussiones Mathematicae Graph Theory2021
HAL back to text
29 articleJ.-C.Jean-Claude Bermond, F.Frédéric Giroire and N.Nicolas Nisse. Graphes et Télécommunications.Bibliothèque TangenteHors Serie 752021, 120-125
HAL back to text
30 articleA.Ali Dehghan and F.Frédéric Havet. On the semi-proper orientations of graphs.Discrete Applied Mathematics296June 2021, 9-25
HAL DOI back to text
31 articleG.Giuseppe Di Lena, A.Andrea Tomassilli, D.Damien Saucez, F.Frédéric Giroire, T.Thierry Turletti and C.Chidung Lac. Distrinet: a Mininet Implementation for the Cloud.Computer Communication Review511January 2021, 2-9
HAL DOI back to text
32 articleN.Nemanja Draganić, F.François Dross, J.Jacob Fox, A.António Girão, F.Frédéric Havet, D.Dániel Korándi, W.William Lochet, D. M.David Munhá Correia, A.Alex Scott and B.Benny Sudakov. Powers of paths in tournaments.Combinatorics, Probability and Computing2021, 1-5
HAL DOI back to text
33 articleF.François Dross and F.Frédéric Havet. On the unavoidability of oriented trees.Journal of Combinatorial Theory, Series B151November 2021, 83-110
HAL DOI back to text
34 articleH.Huy Duong, B.Brigitte Jaumard, D.David Coudert and R.Romualdas Armolavicius. Efficient Make-Before-Break Layer 2 Reoptimization.IEEE/ACM Transactions on Networking295October 2021, 1910-1921
HAL DOI back to text
35 articleM.Matteo Frigo, E.Emilio Cruciani, D.David Coudert, R.Rachid Deriche, S.Samuel Deslauriers-Gauthier and E.Emanuele Natale. Network alignment and similarity reveal atlas-based topological differences in structural connectomes.Network NeuroscienceMay 2021
HAL DOI back to text back to text
36 articleA.Adrien Gausseran, F.Frederic Giroire, B.Brigitte Jaumard and J.Joanna Moulierac. Be Scalable and Rescue My Slices During Reconfiguration.The Computer Journal6410October 2021, 1584-1599
HAL DOI back to text back to text
37 articleA.Adrien Gausseran, A.Andrea Tomassilli, F.Frederic Giroire and J.Joanna Moulierac. Don't Interrupt Me When You Reconfigure my Service Function Chains.Computer Communications171April 2021, 39-53
HAL DOI back to text back to text
38 articleB.Brigitte Jaumard, Y.Yan Wang and D.David Coudert. Dantzig–Wolfe decomposition for the design of filterless optical networks.Journal of Optical Communications and Networking13122021, 10
HAL DOI back to text
39 articleF.Fionn Mc Inerney, N.Nicolas Nisse and S.Stéphane Pérennes. Eternal Domination: D-Dimensional Cartesian and Strong Grids and Everything in Between.Algorithmica8352021, 1459-1492
HAL DOI back to text
40 articleM.Małgorzata Sulkowska, B.Bernhard Gittenberger, Z.Zbigniew Gołębiewski and I.Isabella Larcher. Protection numbers in simply generated trees and Pólya trees.Applicable Analysis and Discrete Mathematics002021, 10-10
HAL DOI back to text
41 articleA.Andrea Tomassilli, G.Giuseppe Di Lena, F.Frédéric Giroire, I.Issam Tahiri, D.Damien Saucez, S.Stéphane Pérennes, T.Thierry Turletti, R.Ruslan Sadykov, F.François Vanderbeck and C.Chidung Lac. Design of Robust Programmable Networks with Bandwidth-optimal Failure Recovery Scheme.Computer Networks192108043June 2021
HAL DOI back to text
42 articleT.Thibaud Trolliet, N.Nathann Cohen, F.Frédéric Giroire, L.Luc Hogie and S.Stéphane Pérennes. Interest clustering coefficient: a new metric for directed networks like Twitter.Journal of Complex Networks2021
HAL DOI back to text
43 articleD.Dimitrios Zorbas, C.Christelle Caillouet, K.Khaled Abdelfadeel Hassan and D.Dirk Pesch. Fast Data Collection in LoRa Networks: a Time-Slotted Approach.Sensors214February 2021, 1193
HAL DOI back to text

International peer-reviewed conferences

44 inproceedingsJ.Julien Bensmail, F.Foivos Fioravantes, F.Fionn Mc Inerney and N.Nicolas Nisse. The Largest Connected Subgraph Game.WG 2021 - The 47th International Workshop on Graph-Theoretic Concepts in Computer Science12911Lecture Notes in Computer ScienceWarsaw, PolandSpringer2021, 296-307
HAL DOI back to text
45 inproceedingsJ.Julien Bensmail, F.Foivos Fioravantes and F.Fionn Mc Inerney. On the Role of 3's for the 1-2-3 Conjecture.CIAC 2021 - 12th International Conference on Algorithms and Complexity12701Lecture Notes in Computer ScienceLarnaca, CyprusSpringer2021, 103-115
HAL DOI back to text
46 inproceedingsA.Andrea Clementi, F.Francesco d'Amore, G.George Giakkoupis and E.Emanuele Natale. Search via Parallel Lévy Walks on $^{2}$ .PODC 2021 - ACM Symposium on Principles of Distributed ComputingSalerno, ItalyInria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France; Università degli Studi di Roma "Tor Vergata"; Univ Rennes, Inria, CNRS, IRISA, FranceApril 2020, 81–91
HAL DOI back to text
47 inproceedingsD.David Coudert, A.André Nusser and L.Laurent Viennot. Hyperbolicity Computation through Dominating Sets.Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022Westin Alexandria Old Town, United StatesJanuary 2022, 78-90
HAL DOI back to text
48 inproceedingsE.Emilio Cruciani, H. A.Hlafo Alfie Mimun, M.Matteo Quattropani and S.Sara Rizzo. Phase Transitions of the $k$ -Majority Dynamics in a Biased Communication Model.ICDCN 2021 - 22nd International Conference on Distributed Computing and NetworkingNara / Virtual, JapanACMJanuary 2021, 146-155
HAL DOI back to text
49 inproceedingsG.Giuseppe Di Lena, A.Andrea Tomassilli, F.Frédéric Giroire, D.Damien Saucez, T.Thierry Turletti and C.Chidung Lac. A Right Placement Makes a Happy Emulator: a Placement Module for Distributed SDN/NFV Emulation.ICC 2021 - IEEE International Conference on CommunicationsMontréal, CanadaIEEEJune 2021
HAL DOI back to text
50 inproceedingsI.Igor Dias Da Silva, C.Christelle Caillouet and D.David Coudert. Optimizing FANET deployment for mobile sensor tracking in disaster management scenario.7th International Conference on Information and Communication Technologies for Disaster Management (ICT-DM)Hangzhou, ChinaIEEEDecember 2021, 134-141
HAL DOI back to text
51 inproceedingsT.Thomas Dissaux, G.Guillaume Ducoffe, N.Nicolas Nisse and S.Simon Nivelle. Treelength of Series-parallel graphs.LAGOS 2021 - XI Latin and American Algorithms, Graphs and Optimization SymposiumSão Paulo / Virtual, BrazilMay 2021
HAL back to text
52 inproceedingsH.Huy Duong, B.Brigitte Jaumard and D.David Coudert. Minimum Disturbance Rerouting to Optimize Bandwidth Usage.ONDM 2021 - International Conference on Optical Network Design and ModelingGothenburg, SwedenIEEEJuly 2021, 1-6
HAL DOI back to text
53 inproceedingsH.Hicham Lesfari, F.Frédéric Giroire, G. D.Giuseppe Di Lena and C.Chidung Lac. A multidimensional colored packing approach for network slicing with dedicated protection.IEEE Global Communications Conference (GLOBECOM)Madrid, SpainDecember 2021
HAL back to text back to text
54 inproceedingsZ.Zhejiayu Ma, S.Soufiane Roubia, F.Frédéric Giroire and G.Guillaume Urvoy-Keller. When Locality is not enough: Boosting Peer Selection of Hybrid CDN-P2P Live Streaming Systems using Machine Learning.Network Traffic Measurement and Analysis Conference (IFIP TMA 2021)Virtual, FranceIFIPSeptember 2021
HAL back to text

National peer-reviewed Conferences

55 inproceedingsA.Ali Al Zoobi, D.David Coudert and N.Nicolas Nisse. De la difficulté de trouver des chemins dissimilaires.ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des TélécommunicationsLa Rochelle, FranceSeptember 2021
HAL back to text
56 inproceedingsJ.Julien Bensmail, F.Foivos Fioravantes, F.Fionn Mc Inerney and N.Nicolas Nisse. Connexions ! Le jeu du plus grand sous-graphe connexe.ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des TélécommunicationsLa Rochelle, France2021
HAL back to text
57 inproceedingsC.Christelle Caillouet, M.Martin Heusse and F.Franck Rousseau. Optimiser l'équité dans les réseaux LoRaWAN.CORES 2021 - 6ème Rencontres Francophones sur la Conception de Protocoles, l’Évaluation de Performance et l’Expérimentation des Réseaux de CommunicationCORES 2021 - 6ème Rencontres Francophones sur la Conception de Protocoles, l’Évaluation de Performance et l’Expérimentation des Réseaux de CommunicationLa Rochelle, FranceMay 2021
HAL back to text
58 inproceedingsT.Thomas Dissaux, G.Guillaume Ducoffe, N.Nicolas Nisse and S.Simon Nivelle. Longueur Arborescente des Graphes Série-Parallèles.ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des TélécommunicationsLa Rochelle, FranceSeptember 2021
HAL back to text
59 inproceedingsH.Hicham Lesfari and F.Frédéric Giroire. Une rencontre entre les noyaux de graphes et la détection d’anomalies dans les réseaux.ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des TélécommunicationsLa Rochelle, FranceSeptember 2021
HAL back to text
60 inproceedingsT.Thibaud Trolliet, F.Frédéric Giroire and S.Stéphane Pérennes. Un modèle de graphes aléatoires croissants pour n'importe quelle distribution des degrés.ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des TélécommunicationsLa Rochelle, FranceSeptember 2021
HAL back to text

Conferences without proceedings

61 inproceedings C.Chuan Xu and G.Giovanni Neglia. What else is leaked when eavesdropping Federated Learning? CCS workshop Privacy Preserving Machine Learning (PPML) Soeul, South Korea November 2021
HAL DOI back to text
62 inproceedingsO.Oualid Zari, C.Chuan Xu and G.Giovanni Neglia. Efficient passive membership inference attack in federated learning.Privacy in Machine Learning - NeurIPS PriML workshopVirtual, FranceDecember 2021
HAL back to text

Scientific book chapters

63 inbookP.Pierre Aboulker, F.Frédéric Havet, K.Kolja Knauer and C.Clément Rambaud. On the dichromatic number of surfaces.14Extended Abstracts EuroComb 2021Trends in MathematicsSpringer International PublishingAugust 2021, 181-187
HAL DOI back to text

Edition (books, proceedings, special issue of a journal)

64 bookD.David Coudert and E.Emanuele Natale. 19th International Symposium on Experimental Algorithms (SEA 2021).Leibniz International Proceedings in Informatics 190Nice, FranceSchloss Dagstuhl -- Leibniz-Zentrum für Informatik; Leibniz-Zentrum für InformatikJune 2021, 434
HAL DOI back to text

Doctoral dissertations and habilitation theses

65 thesisG.Giuseppe Di Lena. Distributed and trustable SDN-NFV-enabled network emulation on testbeds and cloud infrastructures.Université Côte d'AzurMarch 2021
HAL back to text
66 thesisA.Adrien Gausseran. Optimization algorithms for network slicing for 5G.Université Côte d'AzurNovember 2021
HAL back to text
67 thesisV.-H.Viet-Ha Nguyen. Graph problems motivated by (low and high) resolution models of large protein assemblies.I3S, Université Côte d'Azur; ABS, Inria Sophia Antipolis; COATI, Inria Sophia AntipolisDecember 2021
HAL back to text
68 thesisT.Thibaud Trolliet. Study of the properties and modeling of complex social graphs.Université Côte d'AzurJune 2021
HAL back to text

Reports & preprints

69 reportP.Pierre Aboulker, F.Frédéric Havet, K.Kolja Knauer and C.Clément Rambaud. On the dichromatic number of surfaces.Inria; CNRS; I3S; Université Côte D'Azur2021
HAL back to text
70 reportA.Ali Al Zoobi, D.David Coudert and N.Nicolas Nisse. Finding the k Shortest Simple Paths: Time and Space trade-offs.Inria; I3S, Université Côte d'AzurApril 2021
HAL back to text
71 reportA.Ali Al Zoobi, D.David Coudert and N.Nicolas Nisse. On the complexity of finding $k$ shortest dissimilar paths in a graph.Inria; CNRS; I3S; Université Côte d’Azur2021, 9
HAL back to text
72 reportF.Fabricio Benevides, J.-C.Jean-Claude Bermond, H.Hicham Lesfari and N.Nicolas Nisse. Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation.Université Côte d'Azur2021
HAL back to text
73 reportJ.Julien Bensmail, F.François Dross, N.Nacim Oijid and É.Éric Sopena. Generalising the achromatic number to Zaslavsky's colourings of signed graphs.Université côte d'azur; Université de Bordeaux; Université lyon 12021
HAL back to text back to text
74 reportJ.Julien Bensmail, F.Foivos Fioravantes, F.Fionn Mc Inerney, N.Nicolas Nisse and N.Nacim Oijid. The Maker-Breaker Largest Connected Subgraph Game.Université Côte d’Azur, CNRS, Inria, I3S, Biot, France2021
HAL DOI
75 reportJ.Julien Bensmail, F.Foivos Fioravantes, F.Fionn Mc Inerney and N.Nicolas Nisse. The Largest Connected Subgraph Game.Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France; CISPA Helmholtz Center for Information Security, Saarbrücken, Germany2021
HAL back to text
76 reportJ.Julien Bensmail, H.Hervé Hocquard, D.Dimitri Lajou and É.Éric Sopena. A proof of the Multiplicative 1-2-3 Conjecture.Université côte d'azur; Université de bordeaux2021
HAL back to text
77 reportJ.Julien Bensmail, H.Hervé Hocquard, D.Dimitri Lajou and E.Eric Sopena. On a List Variant of the Multiplicative 1-2-3 Conjecture.Université de bordeaux; Université côte d'azur2021
HAL back to text
78 reportJ.Julien Bensmail, H.Hervé Hocquard and P.-M.Pierre-Marie Marcille. Going Wide with the 1-2-3 Conjecture.Université Côte d'Azur; Université de Bordeaux; ENS Lyon2021
HAL back to text
79 reportJ.Julien Bensmail and F.Fionn Mc Inerney. The Vertex-Capturing Game.Université Côte d'Azur; CISPA Helmholtz Center for Information Security2021
HAL back to text
80 reportD.David Coudert, A.Ali Al Zoobi and A.Arthur Finkelstein. On finding $k$ earliest arrival time journeys in public transit networks.InriaJune 2021
HAL back to text
81 reportD.David Coudert, A.André Nusser and L.Laurent Viennot. Enumeration of far-apart pairs by decreasing distance for faster hyperbolicity computation.Inria; I3S, Université Côte d'AzurApril 2021
HAL back to text
82 reportA.Arthur Da Cunha, E.Emanuele Natale and L.Laurent Viennot. Neural Network Information Leakage through Hidden Learning.Inria; CNRS; I3S; Université Côte d'Azur2021
HAL back to text
83 reportG.Giuseppe Di Lena, A.Andrea Tomassilli, F.Frédéric Giroire, D.Damien Saucez, T.Thierry Turletti and C.Chidung Lac. Placement Module for Distributed SDN/NFV Network Emulation.RR-9391Inria Sophia Antipolis - Méditerranée; I3S, Université Côte d'Azur; Orange Labs R&D [Lannion] (France Télécom)February 2021, 32
HAL
84 reportF.Foivos Fioravantes, N.Nikolaos Melissinos and T.Theofilos Triommatis. Complexity of Finding Maximum Locally Irregular Induced Subgraphs.Inria; I3S; Université Côte d'AzurSeptember 2021
HAL back to text
85 reportF.Frédéric Giroire, N.Nicolas Nisse, T.Thibaud Trolliet and M.Malgorzata Sulkowska. Preferential attachment hypergraph with high modularity.Université Cote d'Azur2021
HAL back to text
86 reportF.Frédéric Havet, J.Jørgen Bang-Jensen and A.Anders Yeo. Spanning eulerian subdigraphs in semicomplete digraphs.Inria; CNRS; I3S; Université côte d'azurDecember 2021
HAL back to text
87 reportF.Frédéric Havet, D.Dorian Mazauric and V.-H.Viet-Ha Nguyen. On the complexity of overlaying a hypergraph with a graph with bounded maximum degree.Inria; CNRS; I3S; Université Côte d'Azur2021
HAL back to text
88 reportV.-H.Viet-Ha Nguyen and K.Kévin Perrot. Rikudo is NP-complete.Inria; Université Côte d'Azur; I3S; CNRS2021
HAL back to text
89 reportM.Małgorzata Sulkowska, B.Bernhard Gittenberger, Z.Zbigniew Gołębiewski and I.Isabella Larcher. Counting embeddings of rooted trees into families of rooted trees.Combinatorics, Optimization and Algorithms for Telecommunications [researchteam] (211142); Wrocław University of Science and Technology; Technische Universität WienSeptember 2021
HAL back to text
90 reportM.Małgorzata Sulkowska, A.Alexander Gnedin and P.Patryk Kozieł. Running minimum in the best-choice problem.Wrocław University of Science and Technology; University of London, Queen Mary; Combinatorics, Optimization and Algorithms for Telecommunications [researchteam] (211142)October 2021
HAL
91 report M.Małgorzata Sulkowska, K.Krzysztof Grining and M.Marek Klonowski. What Do Our Choices Say About Our Preferences? Combinatorics, Optimization and Algorithms for Telecommunications [researchteam] (211142); Wrocław University of Science and Technology June 2021
HAL
92 reportM.Małgorzata Sulkowska and M.Michał Lasoń. Modularity of minor-free graphs.Combinatorics, Optimization and Algorithms for Telecommunications [researchteam] (211142); Institute of Mathematics of the Polish Academy of Sciences; Wrocław University of Science and TechnologyFebruary 2021
HAL back to text
93 reportF.Francesco d'Amore, D.Daniel Mitropolsky, P.Pierluigi Crescenzi, E.Emanuele Natale and C. H.Christos H Papadimitriou. Planning with Biological Neurons and Synapses.Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France; Gran Sasso Science Institute (L'Aquila, Italie); Department of Computer Science, Columbia University, New YorkDecember 2021
HAL
94 reportF.Francesco d'Amore and I.Isabella Ziccardi. Phase Transition of the 3-Majority Dynamics with Uniform Communication Noise.Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France; Università degli Studi dell'AquilaDecember 2021
HAL back to text

Other scientific publications

95 inproceedingsE.Emilio Cruciani, F.Francesco d'Amore and E.Emanuele Natale. On some Opinion Dynamics in Multi-Agent Systems.MOMI2021: Le Monde des Mathematiques IndustriellesSophia-Antipolis, FranceMarch 2021
HAL back to text
96 inproceedingsG.Giuseppe Di Lena, F.Frédéric Giroire, T.Thierry Turletti and C.Chidung Lac. CloudTrace Demo: Tracing Cloud Network Delay.IEEE International Conference on Network Softwarization (NetSoft)Fully Virtual, FranceIEEEJune 2021
HAL DOI back to text

11.3 Other

Softwares

97 softwareA.Ali Al Zoobi, D.David Coudert and N.Nicolas Nisse. k shortest simple paths.2021GNU AFFERO General Public License v3.0 or later
HAL Softwage Heritage back to text
98 softwareD.David Coudert, A.André Nusser and L.Laurent Viennot. Hyperbolicity.2021GNU General Public License v3.0 or later
HAL Softwage Heritage back to text

11.4 Cited publications

99 articleS.Spyros Angelopoulos, N.Nicolas Nisse and D. M.Dimitrios M. Thilikos. Preface to special issue on Theory and Applications of Graph Searching.Theoretical Computer Science794November 2019, 1-2
HAL DOI back to text
100 articleJ.Julien Bensmail, T.Thibaut Blanc, N.Nathann Cohen, F.Frédéric Havet and L.Leonardo Rocha. Backbone colouring and algorithms for TDMA scheduling.Discrete Mathematics and Theoretical Computer Science213July 2019, 1-24
HAL back to text back to text back to text back to text
101 articleS.Stephen Finbow, M.-E.Margaret-Ellen Messinger and M. F.Martin F. van Bommel. Eternal domination on 3 ×n grid graphs.Australas. J Comb.612015, 156--174URL: http://ajc.maths.uq.edu.au/pdf/61/ajc_v61_p156.pdf
back to text
102 bookF. V.Fedor V. Fomin, P.Pierre Fraigniaud, N.Nicolas Nisse and D. M.Dimitrios M. Thilikos. Forewords: Special issue on Theory and Applications of Graph Searching Problems.655Part AElsevierDecember 2016
HAL DOI back to text
103 articleI.Ioannis Lamprou, R.Russell Martin and S.Sven Schewe. Eternally dominating large grids.Theor. Comput. Sci.7942019, 27--46URL: https://doi.org/10.1016/j.tcs.2018.09.008
DOI back to text
104 inproceedingsF.Francesco d'Amore, A.Andrea Clementi and E.Emanuele Natale. Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions.SIROCCO 2020 - 27th International Colloquium on Structural Information and Communication Complexity12156SIROCCO 2020. Lecture Notes in Computer Science, vol 12156. SpringerPaderborn, GermanyINRIA Sophia Antipolis - I3S; Università di Roma "Tor Vergata"February 2020, 255--272
HAL DOI back to text back to text

COATI - 2021

COATI - 2021

Keywords

Computer Science and Digital Science

Other Research Topics and Application Domains

1 Team members, visitors, external collaborators

Research Scientists

Faculty Members

Post-Doctoral Fellows

PhD Students

Technical Staff

Interns and Apprentices

Administrative Assistant

Visiting Scientist

External Collaborator

2 Overall objectives

3 Research program

4 Application domains

4.1 Telecommunication Networks

4.2 Other Domains

5 Highlights of the year

5.1 Awards

6 New software and platforms

6.1 New software

6.1.1 FastGRACE

6.1.2 Graph Hyperbolicity

6.1.3 k shortest simple paths

6.1.4 SageMath

6.1.5 JMaxGraph

6.1.6 Idawi

6.1.7 OnlineGraph

7 New results

7.1 Network Design and Management

7.1.1 Network slicing and Network Function Virtualization

Reconfiguration of slices

Protection against failures

Emulation of SDN networks

7.1.2 Optical networks

Make-before-break reoptimization in optical networks

Dantzig-Wolfe Decomposition for the Design of Filterless Optical Networks

7.1.3 Optimization of LoRa networks for the IoT

7.1.4 Optimizing drone coverage

7.1.5 Optimizing the exchange of data

Peer-to-peer networks

Cloud networks

Traffic monitoring and anomaly detection

7.2 Graph Algorithms

7.2.1 Complexity of graph problems

Treelength of series-parallel graphs

The k shortest simple paths problem with dissimilarity constraints

Complexity of finding maximum locally irregular induced subgraphs

7.2.2 Combinatorial games in graphs

Eternal domination game on graphs

Protection numbers in simply generated trees and Pólya trees

The largest connected subgraph game

The vertex-capturing game

Bootstrap percolation and the game of life

Rikudo is NP-complete

Complexity of Games Compendium

7.2.3 Algorithm engineering

Algorithms for the k shortest simple paths problem

Gromov hyperbolicity

7.2.4 Algorithms for social networks

Interest Clustering Coefficient: a New Metric for Directed Networks like Twitter

A Random Growth Model with any Real or Theoretical Degree Distribution

Preferential attachment hypergraph with high modularity

7.2.5 Distributed algorithms

Parallel Lévy walks

Phase transitions of the k-majority dynamics in a biased communication model

3-majority dynamics

On some opinion dynamics in multi-agent systems.

7.3 Graph and digraph theory

7.3.1 Distinguishing labelling problems and the 1-2-3 Conjecture

7.3.2 Graph and digraph colourings

Colouring digraphs

Colouring decorated graphs

Generalising the achromatic number to Zaslavsky's colourings of signed graphs

On BMRN*-colouring of planar digraphs

7.3.3 Graph drawing

7.3.4 Substructures in graphs and digraphs

The $k$ shortest simple paths problem with dissimilarity constraints

Algorithms for the $k$ shortest simple paths problem

Phase transitions of the $k$ -majority dynamics in a biased communication model

On ${BMRN}^{*}$ -colouring of planar digraphs