COATI

COATI - 2023

2023Activity reportProject-TeamCOATI

RNSR: 201322124W

Research center Inria Centre at Université Côte d'Azur
In partnership with:CNRS, Université Côte d'Azur
Team name: 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

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]
Jean-Claude Bermond [CNRS, Emeritus, HDR]
Frédéric Giroire [CNRS, Senior Researcher, HDR]
Frédéric Havet [CNRS, Senior Researcher, HDR]
Emanuele Natale [CNRS, Researcher]
Nicolas Nisse [Inria, Senior Researcher, promoted in Oct. 2023, HDR]
Andre Nusser [CNRS, Researcher, from Dec 2023]
Stéphane Pérennes [CNRS, Senior Researcher, HDR]

Faculty Members

Julien Bensmail [Université Côte d'Azur, Associate Professor, HDR]
Christelle Caillouet [Université Côte d'Azur, Associate Professor, Delegation Inria until 31/08/2023]
Alexandre Caminada [Université Côte d'Azur, Professor, HDR]
Joanna Moulierac [Université Côte d'Azur, Associate Professor, Delegation Inria since 01/09/2023]
Michel Syska [Université Côte d'Azur, Associate Professor]
Chuan Xu [Université Côte d'Azur, Associate Professor]

Post-Doctoral Fellows

Caroline Brosse [CNRS, Post-Doctoral Fellow, from Oct 2023]
Nicolas De Almeida Martins [UFC Fortaleza, from Nov 2023, funded by CAPES]
Damien Rivet [Inria, Post-Doctoral Fellow, until Jun 2023]

PhD Students

Arthur Carvalho Walraven Da Cunha [Inria, until Sep 2023]
Tiago Da Silva Barros [Université Côte d'Azur]
Igor Dias Da Silva [Inria, until Sep 2023]
Thomas Dissaux [Université Côte d'Azur, until Sep 2023]
Ilias Driouich [Amadeus, CIFRE, until Sep 2023]
Henrique Lovisi Ennes [Université Côte d'Azur, from Oct 2023]
Lucas Picasarri Arrieta [Université Côte d'Azur]
Clement Rambaud [ENS Paris, from Oct 2023]
Aurora Rossi [Université Côte d'Azur]

Interns and Apprentices

Justine Cauvi [Inria, Intern, from Jun 2023 until Jul 2023]
Mael Clergue [Inria, Intern, from Jun 2023 until Aug 2023]
Paulo Bruno De Sousa Serafim [GSSI L'Aquila, Intern, until Mar 2023]
Davide Ferre [Inria, from Feb 2023, Relais thèse]
Lilian Fortas [Inria, Intern, from Aug 2023]
Clement Rambaud [ENS Paris, Intern, until Mar 2023]
Teiki Rigaud [ENS Paris, Intern, from Jun 2023 until Aug 2023]
Pietro Ventrella [Inria, Intern, from Mar 2023 until Aug 2023]

Administrative Assistant

Patricia Riveill [Inria]

Visiting Scientists

Pierre Aboulker [ENS Paris, until Mar 2023, Associate Professor]
Joergen Bang Jensen [University of Southern Denmark, from May 2023 until May 2023, Professor]
Zheng Chen [Linkoping University, from Jun 2023 until Jun 2023, Associate Professor]
Pierluigi Crescenzi [GSSI L'Aquila, from Apr 2023 until Jul 2023, Professor]
Andrea D'Ascenzo [University of L'Aquila , from Sep 2023 until Nov 2023, PhD student]
Fabien Dufoulon [Lancaster University, from Sep 2023 until Oct 2023, Associate Professor]
Florian Horsch [CISPA Saarbrücken , from Jun 2023 until Jun 2023, Post-doctoral fellow]
Takako Kodate [Tokyo Woman's Christian University, Japan, from Feb 2023 until Mar 2023]
Amos Korman [FILOFOCS, from Aug 2023 until Aug 2023, Senior Researcher]
Claudia Linhares Sales [UFC Fortaleza, from Dec 2023, Professor]
William Lochet [LIRMM, until Mar 2023, CNRS]
Ana Karolinna Maia [UFC Fortaleza, from Dec 2023, Associate Professor]
Ido Nachum [EPFL, from Jun 2023 until Jul 2023, Post-doctoral fellow]
André Nusser [University of Copenhagen, from Feb 2023 until Feb 2023, Postdoc]
Malgorzata Sulkowska [University of Wroclaw, from May 2023 until May 2023, Associate Professor]
Raul Wayne Texeira Lopes [LIRMM, until Feb 2023, Post-doctoral fellow]

External Collaborator

Michel Cosnard [Université Côte d'Azur, Emeritus Professor, HDR]

2 Overall objectives

Coati is a joint team between the Inria Centre at Université Côte d'Azur and the I3S laboratory (Informatique Signaux et Systèmes de Sophia Antipolis), which belongs to CNRS (Centre National de la Recherche Scientifique) and Université 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 that 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 our 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 optimally solve practical instances 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, etc. 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 8.5) such as structural biology, transportation networks, economy, sociology, etc. For instance, we collaborate with Inria project-team CRONOS (Computational modelling of brain dynamical networks) from Sophia Antipolis in the field of computational neuro-sciences. 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.

These collaborations benefit to the above mentioned domains via the dissemination of our tools. Also, 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.
The research done in Coati results in the production of software (WorlDynamics.jl, etc.), and in the contribution to large open-source softwares such as Sagemath.

Note also that besides our research activity, we are deeply involved in Terra Numerica and contribute to disseminating our domain towards a general audience.

4 Application domains

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

4.1 Telecommunication 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 and with project-team CRONOS (formerly ATHENA) on problems arising in computational neurosciences. 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 curricula (studies and career paths of persons). Last, we collaborate 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 Social and environmental responsibility

5.1 Footprint of research activities

Joanna Moulierac is member of the I3S CO2 group since 2019. The objective of this working group is to evaluate the environmental impact of our research activities and to propose ways to make them evolve by 2030, in order to fulfill the Paris agreements (www.i3s.unice.fr/co2/).

6 Highlights of the year

6.1 New team member

André Nusser has been recruited as CRCN CNRS, section 7, at the I3S laboratory and he joined the team in December 2023;

6.2 Promotions

Nicolas Nisse has been promoted Senior Researcher (Directeur de Recherche) in October 2023;

7 New software, platforms, open data

7.1 New software

7.1.1 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), the Node Classification (NC) algorithm proposed by Feng, the Sidetrack Based (SB) algorithm proposed by Kurz and Mutzel, and variants of SB proposed by Al Zoobi, Coudert and Nisse to reduce running time (improved SB, SB*) and memory usage (Parsimonious SB, PSB). It also implements the Postpone Node Classification (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-03196830v2, hal-03196830, hal-03438331
Contact:
David Coudert
Participants:
David Coudert, Nicolas Nisse, Ali Al Zoobi

7.1.2 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, 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 contributes the improvement and maintenance of the graph module and its 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

7.1.3 WorldDynamics.jl

Name:
WorldDynamics.jl
Keywords:
Integrated assessment modeling, Scientific computing, Julia programming language
Scientific Description:
The World Dynamics project aims to provide a modern framework to investigate integrated assessment models of sustainable development, based on current software engineering and scientific machine learning techniques. Our group is developing a Julia library to allow scientists to easily use and adapt different world models, from Meadows et al.'s World3 to recent proposals. By enabling an open, interdisciplinary, and consistent comparative approach to scientific model development, our goal is to inform global policy makers on environmental and economic issues.
Functional Description:

Integrated Assessment Modeling is a research area that focuses on developing and applying integrated models of human and earth systems to help understand how key aspects of society may evolve in the future and how they might interact with the natural environment and with a changing climate.

Despite the importance of the field, there has been no general software framework which allows scientists to investigate integrated assessment models of sustainable development, by using and adapting the most famous world models, from Meadows et al.'s World3 to recent proposals.

WorldDynamics.jl is a new software library written by members of the COATI Team, that aims to fill such crucial gap, by providing a modern framework in the Julia programming language based on current software engineering and scientific machine learning techniques.
URL:
https://github.com/worlddynamics/WorldDynamics.jl
Contact:
Emanuele Natale
Participants:
Pierluigi Crescenzi, Paulo Bruno De Sousa Serafim, Aurora Rossi, Hicham Lesfari, Emanuele Natale
Partner:
Gran Sasso Science Institute

7.1.4 Idawi

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

Idawi is a middleware for the development and experimentation of distributed applications for multi-hop dynamic networks, such as the IoT, the Edge, Mobile Ad hoc Networks, etc. Such networks can be represented by mixed (featuring both directed and undirected edges) dynamic multi-graphs.

The development of Idawi was initially motivated by the need of the COATI Research group to deploy scientific applications in clusters of computers, in order to run large experimentation campaigns of graph algorithms. Idawi is an innovative arrangement of many features found in existing tools into a fresh Open Source Java reference implementation, but it our Research context we were led to introduce new features and ideas not found in other middleware solutions for distributed computing - such as a fully decentralized network model, a by-default collective communication/computation model, etc.

These naturally turned Idawi into a Research software platform for the experimentation of middleware-level techniques.

Idawi defines applications elements as components organized into a multi-hop overlay network on top of agnostic transport layers such as TCP, UDP and SSH (to enable component deployment and communication even in the presence of NATs and firewalls). In the usual use case, there will be only one component per device. But, in order to enable the simulation/emulation of large systems, components can deploy other components in their Java Virtual Machine (JVM) or in another JVM(s) in the same device.

Idawi proposes a structuring model of distributed applications, which then must conform to a specific Object-Oriented model in the style of SOA: it defines that components expose their functionality via services. Services hold data and implement functionality about the specific concern they are about. Functionality is then exposed via operations, which can be triggered remotely from anywhere in the component overlay.

The decentralized communication model of Idawi matches the very nature of mobile multi-hop networks. It defines that components communicate with each other via messages of bounded size. Messaging can be both synchronous (imperative) and asynchronous (reactive/event-driven). It is powered by a default routing scheme and APIs that are tailored to collective communication, so as to offer native support of parallel processing.

Idawi comes with a set of built-in fully decentralized services for automatized quick deployment/bootstrapping of components through SSH, interoperability through a REST-based web interface, service provisioning and discovery, overlay management, and many other system-level functionality.

In 2023, Idawi was completely refactored so as to introduce the notion of "digital twin" as the core of its network management model. This idea is that the environment of a component is represented by a digital twin — each remote component being represented by a local twin counterpart. Messages can then be configured to be delivered to a twin or to the real component. Doing this smoothens the API and enables any component to simulate distributed processes.
URL:
https://github.com/lhogie/idawi
Publications:
hal-03863333, hal-03886521, hal-03562184
Contact:
Luc Hogie

7.1.5 OnlineGraph

Keywords:
Java, Distributed computing, Graph algorithmics
Functional Description:

OnlineGraph is a decentralized mixed graph library. OnlineGraph is designed and developed as a specific application-level service of the Idawi middleware. It implements a decentralized application distributed over a multi-hop overlay network of components. In this application dedicated to the storage, edition and graphical rendering of graphs, graphs are partitioned over the set of components. The application imposes no allocation strategy: it is left to the application. A graph may be entirely allocated on one specific component, or a subset of the components forming the application, or all of them.

Any component in the application can expose graphs to the Web—not just its component-local part, but all the parts it has access to in the overlay networks. Graphs are then accessible to clients through a set of Web servers exposing services.

A component-local part of a partitioned graph consists of three correlated sets: the vertex set, the arc set, and the edge set. These sets can store the elements they contain in RAM or on disk, thereby enabling persistence. In these sets, graph elements are represented by a 64-bit numerical ID, and they can be associated to any data. This graph data structures can be used out of the distributed infrastructure, just any graph library.

OnlineGraph is developed within the COATI Research group at Inria Sophia Antipolis and I3S Computer Science Laboratory of Université Côte d'Azur.
URL:
https://github.com/lhogie/OnlineGraph
Contact:
Luc Hogie

7.2 Open data

7.2.1 Temporal brain networks

Participants: Emanuele Natale, Aurora Rossi.

The Temporal Brain Networks dataset 77 contains networks representing the brain activity of 1047 subjects. These networks are derived from resting-state functional Magnetic Resonance Imaging (fMRI) data from the Human Connectome Project (HCP). Network nodes represent brain regions, and edges represent the correlation of a window of two brain region activity values. The networks are undirected and weighted. The diagonal values are always 1 because they represent the correlation of a brain region with itself. The number of nodes remains constant over time, while the weights of the edges change. The dataset can be used to investigate brain activity as a temporal graph, it can be found in the Inria space on the Recherche Data Gouv Platform ( https://entrepot.recherche.data.gouv.fr/dataset.xhtml?persistentId=doi%3A10.57745%2FPR8VUV).

This dataset has been assembled in collaboration with Samuel Deslauriers-Gauthier (CRONOS).

7.2.2 Labeled temporal brain networks

Participants: Aurora Rossi.

The Labeled Temporal Brain Networks dataset contains a collection of temporal brain networks from 100 subjects. Each subject is labeled with their biological sex (M for male and F for female) and age range (22-25, 26-30, 31-35, and 36+). The networks are obtained from resting-state fMRI data from the Human Connectome Project (HCP) and are undirected and weighted. The number of nodes is fixed at 202, while the edge weights vary over time. The dataset is labeled and intended for use in machine learning tasks, specifically related to temporal graph neural network architectures. It can be found in the Inria space on the Recherche Data Gouv Platform ( https://entrepot.recherche.data.gouv.fr/dataset.xhtml?persistentId=doi:10.57745/HHNT10).

8 New results

8.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, etc.) or virtual (logical). The objective is to design a network able to route a (given, estimated, dynamic, etc.) 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 or LoRa networks, and of new usages like Internet of Things (IoT), high quality video streaming. Furthermore, the development of machine-learning based methods brings new tools that can help solving optimization problems. 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 efficiently route and place virtual resources in networks?
How to use efficiently wireless networks?
How to use machine-learning based methods for solving network optimization problems?

This very wide topic is considered by a lot of academic and industrial teams in the world. Our approach is to tackle these problems with tools from operations research and discrete mathematics (some of them developed in our teams, see Sections 8.2 and 8.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.

8.1.1 What is the carbon footprint of one hour of video streaming?

Participants: Joanna Moulierac.

Video streaming traffic dominates the Internet traffic. In such a context, assessing the carbon footprint of video streaming has received recently a significant attention with a number of models proposed to associate a CO2 cost to one hour of streaming. The topic is even becoming sensitive, as highlighted by the recent debate between the SHIFT project in France and the International Energy Agency (IEA) experts. Our objective in this work is to compare the modeling assumptions and computation methods used by a number of recent works to inform the debate. Indeed, initial results can be at odds, with up to one order of magnitude difference in the results.

In 74, we focus on five different models. Our contributions are: (i) we relate the difference in the results primarily to the perimeter of the study, e.g. including grey energy (production cost) or not; (ii) we demonstrate that some of the assumptions, while necessary, are difficult to estimate due to a lack of public data; (iii) we question some of the modeling assumptions made using a real deployment of a streaming server in a controlled environment with up to 2000 clients; (iv) we propose a technique to reconcile the models and obtain a CO2 estimate in between 60 and 400 grams when considering the average worldwide electricity efficiency.

8.1.2 Machine learning for video streaming systems

Participants: Frédéric Giroire.

HTTP-based streaming has become the dominant technology for streaming due to the widespread adoption of the HTTP protocol. Many streaming providers use a combination of Content Delivery Network (CDN) and Viewer-to-Viewer (V2V) technology, known as Hybrid CDN/V2V live streaming, for both efficiency and cost-effectiveness. V2V technology allows for offloading streaming traffic from the CDN and reducing operational costs, and WebRTC technology facilitates direct V2V transfer, as it is natively supported by all browsers. In a WebRTC-based V2V network, some viewers cache the video chunks on their devices, while others wait and fetch chunks from their neighbors. A common strategy used to determine when a viewer should stop waiting for chunk delivery and revert to the CDN is called Random Waiting Time Control (RWC). However, due to the complex dynamics in the V2V system, RWC is far from optimal. In 50, we have formulated the Waiting Time Control determination problem as a reinforcement learning problem and proposed a Q-learning-based Waiting Time Control (QWC) solution. We conducted offline experiments in the Grid5000 84 testbed and validated our results through a 14-day A/B testing in the wild. Our findings showed that QWC improves overall streaming Quality-of-Experience (QoE) in rebuffering (-29% fewer events), video quality (+17% higher), and buffer length (+5% longer), with a slightly improved V2V ratio (+5% more).

This is a collaboration with Zhejiayu Ma and Sofiane Rouibia from EasyBroadcast and Guillaume Urvoy-Keller (I3S).

8.1.3 Learning-based packet routing

Participants: Tiago da Silva Barros.

PRISMA: A Packet Routing Simulator for Multi-Agent Reinforcement Learning

In 35, we present PRISMA-v2, a new release of PRISMA 82, 81, a Packet Routing Simulator for Multi-Agent Reinforcement Learning. PRISMA-v2 brings a new set of features. First, it allows simulating overlay network topologies, by integrating virtual links. Second, this release offers the possibility to simulate control packets, which allows to better evaluate the overhead of the network protocol. Last, we integrate the modules along with the core (ns-3) to a docker container, so that it can be run in any machine or platform. PRISMA-v2 is, to the best of our knowledge, the first realistic overlay network simulation playground that offers to the community the possibility to test and evaluate new network protocols.

This work has been done in collaboration with Lucile Sassatelli from SIS team of I3S laboratory.

8.1.4 Modeling 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 (IoT) 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 Martin Heusse and Andrzej Duda (Drakkar, LIG, Grenoble), we present a model for frame delivery rates in LoRaWAN when the gateway is capable of receiving antenna diversity 48. Based on this model, we investigate the level of transmission redundancy required to guarantee reliable data reception without overloading the channel. We then show that receive antenna diversity combined with a well-chosen level of transmission redundancy guarantees maximum channel utilization while maintaining reliable reception of application data.

We also explore the capacity limits and the tradeoff between the antagonistic means of enabling reliable data delivery in a loaded LoRaWAN cell 33. In fact, channel attenuation and variability call for robust transmission settings but the associated load increase causes more collisions between frames. In addition to the physical layer parameters of the LoRa modulation, this work considers the benefits and tuning of inter-packet Error Correction Codes (ECC), which also trades transmission redundancy for reliability. We propose a refined Packet Delivery Ratio (PDR) model that improves the ones found in the literature in that, first, it takes into account the dependency between overcoming ambient noise and dominating colliding frames; and second, it considers the sum of interference powers when multiple colliding frames are present, even if the interference preexists. Moreover, the model extends to the case of a gateway with receiver diversity. In a second step, the model allows to set out the level of redundancy at which ECC is the most effective without hindering capacity: a coding rate of one third. When this is fixed, it allows to define the transmission parameters allocation within a cell and thus the size of the cell.

8.1.5 Aerial networks for sensor coverage and energy harvesting

Participants: Christelle Caillouet, Igor Dias da Silva.

The problem of the lifetime of connected objects, in most use cases (Industrial Internet of Things (IIoT), disaster management, etc.) is an essential element of the proposed solutions. Radio frequency (RF) harvesting of sensor batteries is an attractive solution, however, it does not scale up if it has to be done by human operators, and becomes impossible if the objects are located in unreachable places. An innovative solution consists of using fleets of drones to take care of this regular recharge. In collaboration with Yann Busnel (IMT Nord Europe) 55, we propose a two-stage optimization framework for determining near-optimal trajectories for unmanned aerial vehicles (UAVs), or drones, in order to rapidly recharge a ground-based sensor network, thereby increasing its lifetime. The chosen wireless radio-frequency (RF) charging solution enables multiple sensors to be charged in parallel by a single UAV. However, when several drones charge the same sensor simultaneously, there is a high energy loss. We therefore optimize the flight plan of the drone fleet to minimize the time needed to charge all the sensors, while avoiding this wastage.

8.1.6 Gossiping with interference in radio ring networks

Participants: Jean-Claude Bermond.

In collaboration with Takako Kodate (Tokyo Woman's Christian University, Japan) and Joseph Yu (University of the Fraser Valley, B.C., Canada), we tackled in 27 the problem of gossiping with interference constraint in radio ring networks. Gossiping (or total exchange information) is a protocol where each node in the network has a message and is expected to distribute its own message to every other node in the network. The gossiping problem consists in finding the minimum running time (makespan) of a gossiping protocol and algorithms that attain this makespan. We focus on the case in which the transmission network is a ring network. We consider synchronous protocols where it takes one unit of time (step) to transmit a unit-length message. During one step, a node receives at most one message only through one of its two neighbors. We also suppose that, during one step, a node cannot be both a sender and a receiver (half duplex model). Moreover communication is subject to interference constraints. We use a primary node interference model where, if a node receives a message from one of its neighbors, its other neighbor cannot send at the same time. With these assumptions we completely solve the problem for ring networks. We first show lower bounds and then present gossiping algorithms that meet these lower bounds and so are optimal. The number of rounds depends on the congruences of $n$ modulo 12.

8.1.7 A middleware for the experimentation on IoT mobile networks - a decentralized Web backend

Participant: Luc Hogie [.

Idawi (see Section 7.1.4) is a research software platform for the experimentation of Edge Computing algorithms, whose the infrastructure network can be represented by a mixed (featuring both directed and undirected edges) dynamic multi-graph.

The development of Idawi was initially motivated by the need of Coati to deploy scientific applications in clusters of computers, in order to run large experimentation campaigns of graph algorithms, and it progressively turned to a research platform for decentralized algorithms/systems.

In order to enable the Idawi middleware interoperability with Web appplications, and in particular to build a user Web interface for the control of running distributed computations, we introduced into the middleware a specific service. The role of the service is bridge Web (HTTP/JSON) queries to the internal messaging system of Idawi. The very decentralized nature of Idawi allowed us to design and implement a novel architecture for a Web backend that consists of a set of application-specific services accessible via bridge services available in one or several component of the Idawi system. This enables the resulting decentralized Web backend to be accessible from anywhere, regardless of the presence of network obstacles (NATs, firewall), and to natively support redundancy 49.

8.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 approximations, 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 87, 83, organization of the 11th edition of GRASTA in October 2023, etc.). 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 that satisfies some condition based on their initial input state.

8.2.1 Complexity of graph problems

Participants: Jean-Claude Bermond, Michel Cosnard, David Coudert, Thomas Dissaux, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta.

Leanness of graphs

Let $u$ and $v$ be vertices in a connected graph $G = (V, E)$ . For any integer $k$ such that $0 \leq k \leq {dist}_{G} (u, v)$ , the $k$ -slice $S_{k} (u, v)$ contains all vertices $x$ on a shortest $u v$ -path such that ${dist}_{G} (u, x) = k$ . The leanness of $G$ is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as “interval thinness” and “fellow traveler property”. Graphs with leanness equal to 0, a.k.a. geodetic graphs, also have received special attention in graph theory. The practical computation of leanness in real-life complex networks has been studied recently 88. In collaboration with Samuel Coulomb (ENS Paris) and Guillaume Ducoffe (IRO, Bucharest, Romania), we give in 69 a finer-grained complexity analysis of two related problems, namely: deciding whether the leanness of a graph $G$ is at most some small value $ℓ$ ; and computing the leanness on specific graph classes. We obtain improved algorithms in some cases, and time complexity lower bounds under plausible hypotheses.

New lower bounds on the cutwidth of graphs

Cutwidth is a parameter used in many layout problems. Determining the cutwidth of a graph is an NP-complete problem, but it is possible to design efficient branch-and-bound algorithms if good lower bounds are available for cutting branches during exploration. Knowing how to quickly evaluate good bounds in each node of the search tree is therefore crucial. In 54, we present new lower bounds based on different graph density parameters. We also propose a lower bound based on the grooming of traffic requests on the path.

Constrained flows in networks

The support of a flow $x$ in a network is the subdigraph induced by the arcs $i j$ for which $x_{i j} > 0$ . In 66, we discuss a number of results on flows in networks in which we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example, deciding whether a network $𝒩 = (D, s, t, c)$ has a maximum flow $x$ such that the maximum out-degree of the support $D_{x}$ of $x$ is at most 2 is NP-complete as it contains the 2-linkage problem as a very special case. Another problem that is NP-complete for the same reason is that of deciding the maximum flow we can send from $s$ to $t$ along 2 paths (called a maximum 2-path-flow) in $𝒩$ . Baier et al. (2005) gave a polynomial algorithm which finds a 2-path-flow $x$ whose value is at least $\frac{2}{3}$ of the value of a optimum 2-path-flow. This is best possible unless P=NP. They also obtained a $\frac{2}{p}$ -approximation for the maximum value of a $p$ -path-flow for every $p \geq 2$ . In 66, we present an algorithm that gets within a factor $\frac{1}{H (p)}$ of the optimum solution, where $H (p)$ is the $p$ 'th harmonic number ( $H (p) \sim ln (p)$ ). This improves the approximation bound due to Baier et al. when $p \geq 5$ . We show that in the case in which the network is acyclic, we can find a maximum $p$ -path-flow in polynomial time for every $p$ . We determine the complexity of a number of related problems concerning the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some sense best possible.

Treelength of series–parallel graphs

The length of a tree-decomposition of a graph is the maximum distance (in the graph) 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 size of a largest isometric cycle. This work initiates the study of treelength in planar graphs by considering the next natural subclass of planar graphs, namely the one of series-parallel graphs.

We first fully describe 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 quadratic-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 an infinite family of forbidden isometric subgraphs 31.

8.2.2 Combinatorial games in graphs

Participants: Julien Bensmail, Jean-Claude Bermond, Michel Cosnard, Frédéric Havet, Nicolas Nisse.

Recontamination helps a lot to hunt a rabbit

The Hunters and Rabbit game is played on a graph $G$ in which the Hunter player shoots at $k$ vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if it can ensure that its position is never shot. The Hunter player wins otherwise. The hunter number $h (G)$ of a graph $G$ is the minimum integer $k$ such that the Hunter player has a winning strategy (i.e., allowing him to win whatever be the strategy of the Rabbit player). This game has been studied in several graph classes, in particular in bipartite graphs (grids, trees, hypercubes, etc.), but the computational complexity of computing $h (G)$ remains open in general graphs and even in more restricted graph classes such as trees. To progress further in this study, we propose in 73, 44 a notion of monotonicity (a well-studied and useful property in classical pursuit-evasion games such as Graph Searching games) for the Hunters and Rabbit game imposing that, roughly, a vertex that has already been shot "must not host the rabbit anymore". This allows us to obtain new results in various graph classes. More precisely, let the monotone hunter number $m h (G)$ of a graph $G$ be the minimum integer $k$ such that the Hunter player has a monotone winning strategy. We show that $p w (G) \leq m h (G) \leq p w (G) + 1$ for any graph $G$ with pathwidth $p w (G)$ , which implies that computing $m h (G)$ , or even approximating $m h (G)$ up to an additive constant, is NP-hard. Then, we show that $m h (G)$ can be computed in polynomial time in split graphs, interval graphs, cographs and trees. These results go through structural characterizations which allow us to relate the monotone hunter number with the pathwidth in some of these graph classes. In all cases, this allows us to specify the hunter number or to show that there may be an arbitrary gap between $h$ and $m h$ , i.e., that monotonicity does not help. In particular, we show that, for every $k \geq 3$ , there exists a tree $T$ with $h (T) = 2$ and $m h (T) = k$ . We conclude by proving that computing $h$ (resp., $m h$ ) is FPT parameterized by the minimum size of a vertex cover.

Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation

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 18, we consider 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})$ .

The Maker-Breaker largest connected subgraph game

We consider the following 2-player combinatorial game taking a graph $G$ and an integer $k \in ℕ$ as inputs. At every turn, first Alice colours red an uncoloured vertex of $G$ and then Bob colours an uncoloured vertex blue. Once all vertices have been coloured, Alice wins if there exists a red component of order at least $k$ and Bob wins otherwise. This game is a Maker-Breaker version of the Largest Connected Subgraph Game introduced in 86. We are interested in computing $c_{g} (G)$ which is the maximum $k$ such that Alice wins in $G$ whatever Bob does.

We first show that computing $c_{g}$ is PSPACE-complete1 in bipartite graphs with diameter 4, in split graphs and in planar graphs. Then, we focus on A-perfect graphs, namely, graphs for which $c_{g} (G) = ⌈\frac{| V (G) |}{2}⌉$ , i.e., the maximum possible value. While there exist arbitrary large A-perfect $d$ -regular graphs for any $d \geq 4$ , we prove that, surprisingly, no cubic graph with order at least 133 is A-perfect. Moreover, we exhibit sufficient conditions in terms of degree or number of edges for a graph to be A-perfect.

Finally, graph classes where $c_{g}$ is expected to be computable in polynomial time are considered. We show that $c_{g} (G)$ can be computed in polynomial time when $G$ is a $P_{4}$ -sparse graphs (including cographs). We conclude with many open questions. In particular, natural graph classes such that trees and grid-like graphs seem to be more difficult to deal with. We only give partial results, namely, in caterpillars and in the case of some grid-like graphs 21.

Complexity of Maker-Breaker games on edge sets of graphs

In 21, we initiate the study of the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the $H$ -game. Maker wins if she claims the edges of a perfect matching in the first, and a copy of a fixed graph $H$ in the second. We prove that deciding who wins the perfect matching game and the $H$ -game is PSPACE-complete, even for the latter in small-diameter graphs if $H$ is a tree. Toward finding the smallest graph $H$ for which the $H$ -game is PSPACE-complete, we also prove that such an $H$ of order 51 and size 57 exists.

We then give several positive results for the $H$ -game. As the $H$ -game is already PSPACE-complete when $H$ is a tree, we mainly consider the case where $H$ belongs to a subclass of trees. In particular, we design two linear-time algorithms, both based on structural characterizations, to decide the winners of the $P_{4}$ -game in general graphs and the $K_{1, ℓ}$ -game in trees. Then, we prove that the $K_{1, ℓ}$ -game in any graph, and the $H$ -game in trees are both FPT parameterized by the length of the game, notably adding to the short list of games with this property, which is of independent interest.

Another natural direction to take is to consider the $H$ -game when $H$ is a cycle. While we were unable to resolve this case, we prove that the related arboricity- $k$ game is polynomial-time solvable. In particular, when $k = 2$ , Maker wins this game if she claims the edges of any cycle.

8.2.3 Algorithms for social networks

Participants: Frédéric Giroire, Nicolas Nisse, Stéphane Pérennes.

A random growth model with any real or theoretical degree distribution

The degree distributions of complex networks are usually considered to follow a power law distribution. However, it is not the case for a large number of them. We thus propose a new model able to build random growing networks with (almost) any wanted degree distribution 32. 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, the broken power-law, and the geometric distributions. We also use the model on an undirected version of the Twitter network, for which the degree distribution has an unusual shape. We finally show that the divergence of chosen attachment functions is directly linked to the heavy-tailed property of the obtained degree distributions. This is a collaboration with Thibaud Trolliet (TSE).

Preferential attachment hypergraph with vertex deactivation

In the field of complex networks, hypergraph models have so far received significantly less attention than graphs. However, many real-life networks feature multiary relations (coauthorship, protein reactions) may therefore be better modeled by hypergraphs. Also, a recent study by Broido and Clauset suggests that a power-law degree distribution is not as ubiquitous in the natural systems as it was thought so far. They experimentally confirm that a majority of networks (56% of around 1000 networks that undergone the test) favor a powerlaw with an exponential cutoff over other distributions. We address the two above observations by introducing a preferential attachment hypergraph model that allows for vertex deactivations. The phenomenon of vertex deactivations is rare in existing theoretical models and omnipresent in real-life scenarios (social network accounts that are not maintained forever, collaboration networks in which people retire, technological networks in which devices break down). We prove that the degree distribution of the proposed model follows a power-law with an exponential cutoff. We also check experimentally that a Scopus collaboration network has the same characteristic. We believe that our model will predict well the behavior of systems from a variety of domains 46. In collaboration with Małgorzata Sulkowska (Wrocław University of Science and Technology).

8.2.4 Algorithm engineering

Participants: 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 proposed in 1971 89 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. We proposed a new algorithm, the postponed node classification (PNC) algorithm, that combines the best of NC (low memory consumption) and SB (fast computation) 16.

8.3 Graph and digraph theory

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

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

8.3.1 Partitioning and labelling graphs and digraphs

Participants: Julien Bensmail, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Clément Rambaud.

Distinguishing labelling problems and the 1-2-3 Conjecture

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 H. Hocquard, D. Lajou and É. Sopena (LaBRI, Université de Bordeaux), we have investigated 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, building upon earlier studies, 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 some of our works, we also improved previous known results on other variants of the 1-2-3 Conjecture. In particular, in 24, with H. Hocquard and P.-M. Marcille (LaBRI, Université de Bordeaux), we provided more evidence that a degenerate variant (in which only labels 1 and 2 can be assigned, but the resulting sums are only required to induce forests) might hold true. In 38, with the same authors we proved that a weaker form of the 1-2-3 Conjecture (involving coloured labels) holds in graphs defined in terms of particular forbidden structures, graphs for which the 1-2-3 Conjecture was not known to hold.
In a few works, we have also investigated a few aspects of the original 1-2-3 Conjecture. For instance, in 19, we studied the consequences of requiring, through a proper labelling, that all resulting sums appear in an equitable way (i.e., about the same number of times); while, in 25, we studied proper labellings assigning label 1 to the most edges possible, which concern relates to some of the original practical applications behind the 1-2-3 Conjecture.
In 64, 63, 62, through the supervision of several students, we also introduced and investigated a few new variants of the 1-2-3 Conjecture, and studied how they connect to the original problem. In particular, through these three aforementioned works, we considered variants in directed graphs and 2-edge-coloured graphs.
Last, in 22, we also established formally the hardness of building optimal so-called AVD edge-colourings, which notion has received a lot of attention in literature. In particular, we proved that determining the associated chromatic parameter is NP-hard, which is of prime importance given how investigated this notion has been.

Arbitrarily partitionable graphs

In 60, 26, 65, with O. Baudon and M. Boivin (LaBRI, Université de Bordeaux), we have investigated several properties of arbitrarily partitionable graphs (AP graphs for short), which are those graphs that can be vertex-partitioned into arbitrarily many connected subgraphs with arbitrary order. While AP graphs form a superclass of Hamiltonian graphs, we proved results showing both the similarities and the discrepancies between AP graphs and Hamiltonian graphs. In particular, we proved that a few sufficient conditions for Hamiltonicity can be weakened to APness, while we proved some do not, sometimes in a strong sense. We also investigated AP graphs that are minimal w.r.t. the AP property, giving, among others, results on their order, their minimum degree, their maximum degree, and their clique number.

Unbalanced Spanning Subgraphs in Edge Labeled Complete Graphs

Let $K$ be a complete graph of order $n$ . For $d \in (0, 1)$ , let $c$ be a $\pm 1$ -edge labeling of $K$ such that there are $d (\binom{n}{2})$ edges with label $+ 1$ , and let $G$ be a spanning subgraph of $K$ of maximum degree at most $Δ$ and with $m (G)$ edges. In 28, we prove the existence of an isomorphic copy $G^{'}$ of $G$ in $K$ such that the number of edges with label $+ 1$ in $G^{'}$ is at least $(d + \frac{f_{d}}{2 Δ + 1} - O (\frac{1}{n})) m (G)$ for some positive $f_{d}$ depending only on $d$ , that is, this number visibly exceeds its expected value $d \cdot m (G)$ when considering a uniformly random copy of $G$ in $K$ . For $d = \frac{1}{2}$ , and $Δ \leq 2$ , we present more detailed results.

Colouring decorated graphs

In 20 with T. Das, S. Nandi and S. Sen (from various institutes in India), and D. Lajou (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), in particular in the context of various types of grids. The bounds we established apart, we also summarized the state of research of the field to date, and raised new results and questions, to motivate researchers to undertake further studies on the topic.

Colouring digraphs

The dichromatic number $\vec{χ} (D)$ of a digraph $D$ is the minimum number of colours needed to colour the vertices of a digraph such that each colour class induces an acyclic subdigraph.

In 67, we give both lower and upper bounds on the dichromatic number of super-orientations of chordal graphs (i.e. digraphs for which the underlying graph is chordal). When restricted to oriented graphs, we show that the easy bound on the dichromatic number of such digraphs is best possible even for orientations of interval graphs. We then show, for every digraph $D$ in this class, that its dichromatic number is bounded above by $\frac{1}{2} ω + O (\sqrt{d \cdot ω})$ with $d$ the maximum average degree of the symmetric part of $D$ and $ω$ the clique number of $D$ . Finally, we show that if the symmetric part of $D$ contains no $C_{4}$ as a subgraph, then the dichromatic number is bounded above by $⌈\frac{ω + 3}{2}⌉$ . We justify that this is almost best possible upper bound by constructing digraphs in this class with dichromatic number $⌊\frac{ω + 3}{2}⌋$ .

We define $Δ_{max} (D)$ as the maximum of ${max (d^{+} (v), d^{-} (v)) ∣ v \in V}$ and $Δ_{min} (D)$ as the maximum of ${min (d^{+} (v), d^{-} (v)) ∣ v \in V}$ . It is known that the dichromatic number of $D$ is at most $Δ_{min} (D) + 1$ . In 51 and 34, we prove that every digraph $D$ which has dichromatic number exactly $Δ_{min} (D) + 1$ must contain the directed join of $\overset{\leftrightarrow}{K_{r}}$ and $\overset{\leftrightarrow}{K_{s}}$ for some $r, s$ such that $r + s = Δ_{min} (D) + 1$ . In particular, every oriented graph $\vec{G}$ with $Δ_{min} (\vec{G}) \geq 2$ has dichromatic number at most $Δ_{min} (\vec{G})$ .

Let $\vec{G}$ be an oriented graph of order $n$ such that $Δ_{min} (\vec{G}) \leq 1$ . Given two 2-dicolourings of $\vec{G}$ , we show that we can transform one into the other in at most $n$ steps, by recolouring one vertex at each step while maintaining a dicolouring at any step. Furthermore, we prove that, for every oriented graph $\vec{G}$ on $n$ vertices, the distance between two $k$ -dicolourings is at most $2 Δ_{min} (\vec{G}) n$ when $k \geq Δ_{min} (\vec{G}) + 1$ .

We then extend a theorem of Feghali, Johnson and Paulusma to digraphs. We prove that, for every digraph $D$ with $Δ_{max} (D) = Δ \geq 3$ and every $k \geq Δ + 1$ , the $k$ -dicolouring graph of $D$ consists of isolated vertices and at most one further component that has diameter at most $c_{Δ} n^{2}$ , where $c_{Δ} = O (Δ^{2})$ is a constant depending only on $Δ$ .

A digraph $D$ is $k$ -dicritical if $\vec{χ} (D) = k$ and each proper subdigraph $H$ of $D$ satisfies $\vec{χ} (H) < k$ . For integers $k$ and $n$ , we define $d_{k} (n)$ (respectively $o_{k} (n)$ , $g_{k} (n)$ ) as the minimum number of arcs possible in a $k$ -dicritical digraph (respectively oriented graph, bidirected graph). Kostochka and Stiebitz have shown that $d_{4} (n) \geq \frac{10}{3} n - \frac{4}{3}$ . They also conjectured that $d_{k} (n) = g_{k} (n)$ and that there is a constant $c$ such that $o_{k} (n) \geq c d_{k} (n)$ for $k \geq 3$ and $n$ large enough. This conjecture is known to be true for $k = 3$ (Aboulker et al.).

In 76, we prove the first conjecture when $k \leq n \leq 2 k - 1$ . In this particular case, we also characterize the $k$ -dicritical digraphs with exactly $d_{k} (n)$ arcs. This generalizes a result about critical graphs obtained in 1963 by Gallai. In 47, 59, we prove that every 4-dicritical oriented graph on $n$ vertices has at least $(\frac{10}{3} + \frac{1}{51}) n - 1$ arcs, showing the second conjecture for $k = 4$ . We also characterize exactly the 4-dicritical digraphs on $n$ vertices with exactly $\frac{10}{3} n - \frac{4}{3}$ arcs.

Digraph redicolouring

In this work, we generalize several results on graph recolouring to digraphs.

Given two $k$ -dicolourings of a digraph $D$ , we prove that it is PSPACE-complete to decide whether we can transform one into the other by recolouring one vertex at each step while maintaining a dicolouring at any step even for $k = 2$ and for digraphs with maximum degree 5 or oriented planar graphs with maximum degree 6.

A digraph is said to be $k$ -mixing if there exists a transformation between any pair of $k$ -dicolourings. We show that every digraph $D$ is $k$ -mixing for all $k \geq δ_{min}^{*} (D) + 2$ , generalizing a result due to Dyer et al. We also prove that every oriented graph $\vec{G}$ is $k$ -mixing for all $k \geq δ_{max}^{*} (\vec{G}) + 1$ and for all $k \geq δ_{avg}^{*} (\vec{G}) + 1$ . Here $δ_{min}^{*}$ , $δ_{max}^{*}$ , and $δ_{avg}^{*}$ denote the min-degeneracy, the max-degeneracy, and the average-degeneracy respectively.

We pose as a conjecture that, for every digraph $D$ , the dicolouring graph of $D$ on $k \geq δ_{min}^{*} (D) + 2$ colours has diameter at most $O (| V (D) |^{2})$ . This is the analogue of Cereceda's conjecture for digraphs. We generalize to digraphs two results supporting Cereceda's conjecture. We first prove that the dicolouring graph of any digraph $D$ on $k \geq 2 δ_{min}^{*} (D) + 2$ colours has linear diameter, extending a result from Bousquet and Perarnau. We also prove that the analogue of Cereceda's conjecture is true when $k \geq \frac{3}{2} (δ_{min}^{*} (D) + 1)$ , which generalizes a result from Bousquet and Heinrich.

Restricted to the special case of oriented graphs, we prove that the dicolouring graph of any subcubic oriented graph on $k \geq 2$ colours is connected and has diameter at most $2 n$ . We conjecture that every non 2-mixing oriented graph has maximum average degree at least 4, and we provide some support for this conjecture by proving it on the special case of 2-freezable oriented graphs. More generally, we show that every $k$ -freezable oriented graph on $n$ vertices must contain at least $k n + k (k - 2)$ arcs, and we give a family of $k$ -freezable oriented graphs that reach this bound. In the general case, we prove as a partial result that every non 2-mixing oriented graph has maximum average degree at least $\frac{7}{2}$ 29, 68.

8.3.2 Structural digraph theory

Participants: Julien Bensmail, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Clément Rambaud.

One of our goals is to establish structural results on digraphs that can be used to design efficient algorithms. In particular, we are looking for substructures with certain properties or ways to represent or approximate efficiently the digraphs.

Semi-proper orientations of dense graphs

An orientation $D$ of a graph $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation $D$ of a graph $G$ is a $k$ -orientation if the in-degree of each vertex in $D$ is at most $k$ . An orientation $D$ of $G$ is proper if any two adjacent vertices have different in-degrees in $D$ . The proper orientation number of a graph $G$ , denoted by $\vec{χ} (G)$ , is the minimum $k$ such that $G$ has a proper $k$ -orientation.

A weighted orientation of a 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 of $G$ is a weighted orientation $(D, w)$ of $G$ such that for every two adjacent vertices $u$ and $v$ in $G$ , we have that $S_{(D, w)} (v) \neq S_{(D, w)} (u)$ , where $S_{(D, w)} (v)$ is the sum of the weights of the arcs in $(D, w)$ with head $v$ . For a positive integer $k$ , a semi-proper $k$ -orientation $(D, w)$ of a graph $G$ is a semi-proper orientation of $G$ such that ${max}_{v \in V (G)} S_{(D, w)} (v) \leq k$ . The semi-proper orientation number of a graph $G$ , denoted by $\vec{χ_{s}} (G)$ , is the least $k$ such that $G$ has a semi-proper $k$ -orientation.

We first prove that $\vec{χ_{s}} (G) \in {ω (G) - 1, ω (G)}$ for every split graph $G$ , and that, given a split graph $G$ , deciding whether $\vec{χ_{s}} (G) = ω (G) - 1$ is an $N P$ -complete problem. We also show that, for every $k$ , there exists a (chordal) graph $G$ and a split subgraph $H$ of $G$ such that $\vec{χ} (G) \leq k$ and $\vec{χ} (H) = 2 k - 2$ . In the sequel, we show that, for every $n \geq p (p + 1)$ , $\vec{χ_{s}} (P_{n}^{p}) = ⌈\frac{3}{2} p⌉$ , where $P_{n}^{p}$ is the $p^{t h}$ power of the path on $n$ vertices. We investigate further unit interval graphs with no big clique: we show that $\vec{χ} (G) \leq 3$ for any unit interval graph $G$ with $ω (G) = 3$ , and present a complete characterization of unit interval graphs with $\vec{χ} (G) = ω (G) = 3$ . Then, we show that deciding whether $\vec{χ_{s}} (G) = ω (G)$ can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing $\vec{χ_{s}} (G)$ is FPT when parameterized by the minimum size of a vertex cover in $G$ or by the treewidth of $G$ . We also prove that not only computing $\vec{χ_{s}} (G)$ , but also $\vec{χ} (G)$ , admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size $4^{𝒪 (k^{2})}$ and $𝒪 (2^{k} k^{2})$ , in chordal graphs and split graphs, respectively, for the problem of deciding whether $\vec{χ_{s}} (G) \leq k$ parameterized by $k$ . We also present exponential kernels for computing both $\vec{χ} (G)$ and $\vec{χ_{s}} (G)$ parameterized by the value of the solution when $G$ is a cograph. On the other hand, we show that computing $\vec{χ_{s}} (G)$ does not admit a polynomial kernel parameterized by the value of the solution when $G$ is a chordal graph, unless $N P \subseteq c o N P / p o l y$ 36. Collaboration within the Inria EA CANOE and the CAPES-Cofecub project with the PARGO team from UFC, Fortaleza, Brazil.

Deciding the Erdős-Pósa property in 3-connected digraphs

A (di)graph H has the Erdős-Pósa (EP) property for (butterfly) minors if there exists a function $f : ℕ \to ℕ$ such that, for any $k \in ℕ$ and any (di)graph G, either G contains at least k pairwise vertex disjoint copies of H as (butterfly) minor, or there exists a subset T of at most f (k) vertices such that H is not a (butterfly) minor of $G - T$ . It is a well known result of Robertson and Seymour that an undirected graph has the EP property if and only if it is planar. This result was transposed to digraphs by Amiri, Kawarabayashi, Kreutzer and Wollan, who proved that a strong digraph has the EP property for butterfly minors if, and only if, it is a butterfly minor of a cylindrical grid. Contrary to the undirected case in which a graph is planar if, and only if, it is the minor of some grid, not all planar digraphs are butterfly minors of a cylindrical grid. In 37, we characterize the planar digraphs that have a butterfly model in a cylindrical grid. In particular, this leads to a linear-time algorithm that decides whether a weakly 3-connected strong digraph has the EP property. Collaboration within the Inria EA CANOE and the CAPES-Cofecub project with the PARGO team from UFC, Fortaleza, Brazil.

Inversions in digraphs

The inversion of a set $X$ of vertices in a digraph $D$ consists of reversing the direction of all arcs of $D 〈 X 〉$ . We study ${sinv}_{k}^{'} (D)$ (resp. ${sinv}_{k} (D)$ ) which is the minimum number of inversions needed to transform $D$ into a $k$ -arc-strong (resp. $k$ -strong) digraph and ${sinv}_{k}^{'} (n) = max {{sinv}_{k}^{'} (D) ∣ D is a 2 k -edge-connected digraph of order n}$ . In 45, we show :

(i)
$\frac{1}{2} log (n - k + 1) \leq {sinv}_{k}^{'} (n) \leq log n + 4 k - 3$ ;
(ii)
for any fixed positive integers $k$ and $t$ , deciding whether a given oriented graph $\vec{G}$ satisfies ${sinv}_{k}^{'} (\vec{G}) \leq t$ (resp. ${sinv}_{k} (\vec{G}) \leq t$ ) is NP-complete ;
(iii)
if $T$ is a tournament of order at least $2 k + 1$ , then ${sinv}_{k}^{'} (T) \leq {sinv}_{k} (T) \leq 2 k$ , and ${sinv}_{k}^{'} (T) \leq \frac{4}{3} k + o (k)$ ;
(iv)
$\frac{1}{2} log (2 k + 1) \leq {sinv}_{k}^{'} (T) \leq {sinv}_{k} (T)$ for some tournament $T$ of order $2 k + 1$ ;
(v)
if $T$ is a tournament of order at least $19 k - 2$ (resp. $11 k - 2$ ), then ${sinv}_{k}^{'} (T) \leq {sinv}_{k} (T) \leq 1$ (resp. ${sinv}_{k} (T) \leq 3$ );
(vi)
for every $ϵ > 0$ , there exists $C$ such that ${sinv}_{k}^{'} (T) \leq {sinv}_{k} (T) \leq C$ for every tournament $T$ on at least $2 k + 1 + ϵ k$ vertices.

From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows

An s-branching flow f in a network $N = (D, u)$ , where u is the capacity function, is a flow that reaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other than s. Bang-Jensen and Bessy 80 showed that, when every arc has capacity $n - 1$ , a network $N$ admits $k$ arc-disjoint s-branching flows if and only if its associated digraph $D$ contains $k$ arc-disjoints-branchings. Thus a classical result by Edmonds stating that a digraph contains $k$ arc-disjoints-branchings if and only if the indegree of every set $X \subseteq V (D) ∖ s$ is at least $k$ also characterizes the existence of $k$ arc-disjoint s-branching flows in those networks, suggesting that the larger the capacities are, the closer an s-branching flow is from simply being an s-branching. This observation is further implied by results by Bang-Jensen et al. 85 showing that there is a polynomial algorithm to find the flows (if they exist) when every arc has capacity $n - c$ , for every fixed $c \geq 1$ , and that such an algorithm is unlikely to exist for most other choices of the capacities. In 30, we investigate how a property that is a natural extension of the characterization by Edmonds’ relates to the existence of k arc-disjoint s-branching flows in networks. Although this property is always necessary for the existence of the flows, we show that it is not always sufficient and that it is hard to decide if the desired flows exist even if we know beforehand that the network satisfies it. On the positive side, we show that it guarantees the existence of the desired flows in some particular cases depending on the choice of the capacity function or on the structure of the underlying graph of $D$ , for example. We remark that, in those positive cases, polynomial time algorithms to find the flows can be extracted from the constructive proofs. Collaboration within the Inria EA CANOE and the CAPES-Cofecub project with the PARGO team from UFC, Fortaleza, Brazil.

Redicolouring digraphs: directed treewidth and cycle-degeneracy

Given a digraph $D = (V, A)$ on $n$ vertices and a vertex $v \in V$ , the cycle-degree of $v$ is the minimum size of a set $S \subseteq V (D) ∖ {v}$ intersecting every directed cycle of $D$ containing $v$ . From this definition of cycle-degree, we define the $c$ -degeneracy (or cycle-degeneracy) of $D$ , which we denote by $δ_{c}^{*} (D)$ . It appears to be a nice generalization of the undirected degeneracy. For instance, the dichromatic number $\vec{χ} (D)$ of $D$ is bounded above by $δ_{c}^{*} (D) + 1$ , where $\vec{χ} (D)$ is the minimum integer $k$ such that $D$ admits a $k$ -dicolouring, i.e., a partition of its vertices into $k$ acyclic subdigraphs.

In 75, using this new definition of cycle-degeneracy, we extend several evidences for Cereceda's conjecture to digraphs. The $k$ -dicolouring graph of $D$ , denoted by $𝒟_{k} (D)$ , is the undirected graph whose vertices are the $k$ -dicolourings of $D$ and in which two $k$ -dicolourings are adjacent if they differ on the colour of exactly one vertex. This is a generalization of the $k$ -colouring graph of an undirected graph $G$ , in which the vertices are the proper $k$ -colourings of $G$ .

We show that $𝒟_{k} (D)$ has diameter at most $O_{δ_{c}^{*} (D)} (n^{δ_{c}^{*} (D) + 1})$ (respectively $O (n^{2})$ and $(δ_{c}^{*} (D) + 1) n$ ) when $k$ is at least $δ_{c}^{*} (D) + 2$ (respectively $\frac{3}{2} (δ_{c}^{*} (D) + 1)$ and $2 (δ_{c}^{*} (D) + 1)$ ). This improves known results on digraph redicolouring (Bousquet et al.). Next, we extend a result due to Feghali to digraphs, showing that $𝒟_{d + 1} (D)$ has diameter at most $O_{d, ϵ} (n {(log n)}^{d - 1})$ when $D$ has maximum average cycle-degree at most $d - ϵ$ .

We then show that two proofs of Bonamy and Bousquet for undirected graphs can be extended to digraphs. The first one uses the digrundy number of a digraph ${\vec{χ}}_{g} (D)$ , which is the worst number of colours used in a greedy dicolouring. If $k \geq {\vec{χ}}_{g} (D) + 1$ , we show that $𝒟_{k} (D)$ has diameter at most $4 \cdot \vec{χ} (D) \cdot n$ . The second one uses the $D$ -width of a digraph, denoted by $error (D)$ , which is a generalization of the treewidth to digraphs. If $k \geq error (D) + 2$ , we show that $𝒟_{k} (D)$ has diameter at most $2 (n^{2} + n)$ .

Finally, we give a general theorem which makes a connection between the recolourability of a digraph $D$ and the recolourability of its underlying graph $U G (D)$ . Assume that $𝒢$ is a class of undirected graphs, closed under edge-deletion and with bounded chromatic number, and let $k \geq χ (𝒢)$ (i.e., $k \geq χ (G)$ for every $G \in 𝒢$ ) be such that, for every $n$ -vertex graph $G \in 𝒢$ , the diameter of the $k$ -colouring graph of $G$ is bounded by $f (n)$ for some function $f$ . We show that, for every $n$ -vertex digraph $D$ such that $U G (D) \in 𝒢$ , the diameter of $𝒟_{k} (D)$ is bounded by $2 f (n)$ . For instance, this result directly extends a number of results on planar graph recolouring to planar digraph redicolouring. In collaboration with Ignasi Sau (CNRS, LIRMM).

8.3.3 Metric dimension in oriented graphs

The (directed) metric dimension of a digraph $D$ , denoted by $error (D)$ , is the size of a smallest subset $S$ of vertices such that every two vertices of $D$ are distinguished via their distances from the vertices in $S$ .

In 17, we investigate the graph parameters $BOMD (G)$ and $WOMD (G)$ which are respectively the smallest and largest metric dimension over all orientations of $G$ . We show that those parameters are related to several classical notions of graph theory and investigate the complexity of determining those parameters. We show that $BOMD (G) = 1$ if and only if $G$ is hypotraceable (that is has a path spanning all vertices but one), and deduce that deciding whether $BOMD (G) \leq k$ is NP-complete for every positive integer $k$ . We also show that $WOMD (G) \geq α (G) - 1$ , where $α (G)$ is the stability number of $G$ . We then deduce that for every fixed positive integer $k$ , we can decide in polynomial time whether $WOMD (G) \leq k$ .

The most significant results deal with oriented forests. We provide a linear-time algorithm to compute the metric dimension of an oriented forest and a linear-time algorithm that, given a forest $F$ , computes an orientation $D^{-}$ with smallest metric dimension (i.e. such that $error (D^{-}) = BOMD (F)$ ) and an orientation $D^{+}$ with largest metric dimension (i.e. such that $error (D^{+}) = WOMD (F)$ ).

Collaboration within the Inria EA CANOE and the CAPES-Cofecub project with the PARGO team from UFC, Fortaleza, Brazil.

8.4 Machine learning theory and algorithms

Participants: Arthur Carvalho da Cunha, Ilias Driouich, Frédéric Giroire, Emanuele Natale, Aurora Rossi, Chuan Xu.

In the last years, Coati has started investigating machine-learning-based methods to enhance algorithms or solve optimization problems in networks (see e.g., Sections 8.1.2 and 8.1.3). It also investigates how to use tools from graph theory, algorithmic and combinatorics to improve machine-learning tools. We here present our last results in this direction.

New results on the Random Subset Sum problem and the Strong Lottery Ticket Hypothesis

The Strong Lottery Ticket Hypothesis (SLTH) states that randomly-initialized neural networks likely contain subnetworks that perform well without any training. Although unstructured pruning has been extensively studied in this context, its structured counterpart, which can deliver significant computational and memory efficiency gains, has been largely unexplored. One of the main reasons for this gap is the limitations of the underlying mathematical tools used in formal analyses of the SLTH. In 40, we overcome these limitations: we leverage recent advances in the multidimensional generalization of the Random Subset-Sum Problem and obtain a variant that admits the stochastic dependencies that arise when addressing structured pruning in the SLTH. We apply this result to prove, for a wide class of random Convolutional Neural Networks, the existence of structured subnetworks that can approximate any sufficiently smaller network. This result provides the first sub-exponential bound around the SLTH for structured pruning, opening up new avenues for further research on the hypothesis and contributing to the understanding of the role of over-parameterization in deep learning. Furthermore, in 42, we present an alternative proof for the classical result on the Random Subset Sum problem, which has been leveraged in previous proofs of the SLTH. Our new result offer a more direct approach and make use of more elementary tools.

A GPU implementation of the FlyHash approximate search method

FlyHash is a locality-sensitive hashing algorithm inspired by the nervous system of the Drosophila fly. It has demonstrated to be particularly effective for similarity search, especially in the federated context where multiple players collaborate to solve a statistical learning task. FlyHash mainly relies on a process called winner-take-all, which is used to binarize information. However, the implementation of this process is a major challenge and limits the algorithm's usage in processing large data streams. In 41, 72, we propose a simple algorithm to make the winner-take-all operation efficient on GPUs. We create a FlyHash adaptation suitable for the CUDA architecture. We assess the speed of this version experimentally and present a comparison with the CPU version of FlyHash.

Neural network information leakage through hidden learning

In 39, we investigate the problem of making an artificial neural network perform hidden computations whose result can be easily retrieved from the network's output. In particular, we consider the following scenario. A user is provided a neural network for a classification task by a third party. The user's input to the network contains sensitive information and the third party can only observe the output of the network. In this work, we provide a simple and efficient training procedure, which we call hidden learning, that produces two networks: (i) one that solves the original classification task with performance near to state of the art; (ii) a second one that takes as input the output of the first, retrieving sensitive information to solve a second classification task with good 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.

An open-source framework written in Julia for integrated global assessment modeling

Trying to predict the evolution of human society in terms of its fundamental aspects is both a delicate and urgent issue for science. Over the years, a number of models have been developed to help in this respect. In 56, 70, we present WorldDynamics.jl, an open-source framework that includes the software presented in Section 7.1.3, with the aim of enabling scientists to easily use and adapt different integrated assessment models for sustainable development. The library has been developed using the Julia programming language and incorporates different famous integrated assessment models. The implementation provided can directly benefit from a wide range of tools already available in the Julia language ecosystem, including the JuMP modeling language for performing mathematical optimization on aspects of the models.

8.5 Collaborations with other fields

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. In addition, some results motivated by transportation networks are presented in Section 8.2.4.

8.5.1 Analysis of temporal brain networks

Participants: Emanuele Natale, Aurora Rossi.

In collaboration with Samuel Deslauriers-Gauthier (CRONOS) we investigated the properties of temporal brain networks extracted from functional Magnetic Resonance Imaging (fMRI) data from the WU-Minn Human Connectome Project (HCP). We first created and published 78 the dataset that collects the networks (see Section 7.2.1). We presented it with a poster at the annual NeuroMod meeting. We analyzed the dataset focusing on temporal small-worldness. To test certain hypotheses of the observed functional connectivity, we proposed three temporal null models: the geometric euclidean model on a square and on a torus, and the hyperbolic geometric graph model. The hyperbolic model is popular in the research community for studying real-world complex networks. It can model both a high-tailed degree distribution and small-worldness. Our analysis indicates that the hyperbolic model is more effective in reproducing the small-worldness property of real data, making it a favorable null model. We presented our initial findings at the Complex Network Conference 52. A complete version of the work will soon be appearing in the journal Network Neuroscience.

8.5.2 Temporal graph neural networks

Participants: Aurora Rossi.

We collaborated with Carlo Lucibello (Bocconi University, Italy) to contribute to the Julia open source libraries GraphNeuralNetworks.jl and MLDatasets.jl. Our project's objective was to add support for temporal graph neural networks (TGNNs) to GraphNeuralNetworks.jl by creating a temporal graph type. We added new layers to the package and included new datasets of brain connectomes (see Section 7.2.2) and traffic networks in MLDatasets.jl. Tutorials have been created to introduce the new temporal graph type and demonstrate how to perform temporal graph classification using the added data, model, and features. Examples were presented in a poster at the Julia Days in Paris 2023 79.

8.5.3 Distributed algorithms

Participants: Davide Ferré, Nicolas Nisse.

Weakly synchronous systems with three machines are turing powerful

Communicating finite-state machines (CFMs) are a Turing powerful model of asynchronous message-passing distributed systems. In weakly synchronous systems, processes communicate through phases in which messages are first sent and then received, for each process. Such systems enjoy a limited form of synchronization, and for some communication models this restriction is enough to make the reachability problem decidable. In particular, we explore the intriguing case of p2p (FIFO) communication, for which the reachability problem is known to be undecidable for four processes, but decidable for two. We show in 43 that the configuration reachability problem for weakly synchronous systems of three processes is undecidable. This result is heavily inspired by our study on the treewidth of the Message Sequence Charts (MSCs) that might be generated by such systems. In this sense, the main contribution of this work is a weakly synchronous system with three processes that generates MSCs of arbitrarily large treewidth. In collaboration with Cinzia di Giusto and Étienne Lozes (I3S, UniCA).

9 Bilateral contracts and grants with industry

9.1 Bilateral contracts with industry

Amadeus, 2022-2023

Participants: Ilias Driouich, Frédéric Giroire, Chuan Xu.

Collaboration with Amadeus funded by ANR in the context of "plan de relance". It supports the PhD thesis of Ilias Driouich under the co-supervision of Frédéric Giroire and Chuan Xu.
The PhD student has interrupted his PhD in October 2023, thus ending the contract.

10 Partnerships and cooperations

10.1 International initiatives

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

CANOE

Participants: Thomas Dissaux, Frédéric Giroire, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Clément Rambaud.

Title:
Combinatorial Algorithms for Networking prOblEms
Duration:
2023 - 2025
Coordinator:
Nicolas Nisse
Partners:
ParGO Research Group, Department of Mathematics, Federal University of Ceará, Fortaleza, Brazil
Summary:
A graph is a mathematical structure that allows modeling networks in many contexts, from route networks, telecommunication networks, biological networks, neural networks to social networks. There are graph problems arising in each of these domains that are classified as computationally difficult, where the objective is to obtain an efficient algorithm for any graph presented as input. However, studying algorithms for a problem restricted to special graphs can shed light on the problem. This approach consists in assuming that the graph has some special structural property and exploiting this property in the algorithm. Such a structural property defines a class of graphs, for example, trees or planar graphs. The aim is to build an efficient algorithm for a class of graphs, and then explore the ideas used to solve larger and larger classes of graphs or with fewer structural constraints. While a lot of work has been dedicated to the study of structural properties of graphs, very few results are known concerning directed graphs or hypergraphs which better model real life networks. For instance, road networks are intrinsically directed and so are many social networks (e.g., Twitter), co-authorship networks correspond to hypergraphs (where each publication corresponds to an hyperedge gathering the co-authors), etc. This project aims at tackling chalenging theoretical open problems in digraphs and/or hypergraphs. The purpose of this project is also to pursue and extend our fruitful collaboration with the ParGO team from Universidade Federal do Ceara (Fortaleza).
Web:
team.inria.fr/coati/inria-associated-team-canoe/

10.1.2 Participation in other International Programs

CAPES-Cofecub project Ma 1004/23 : Graphs, Optimization, Combinatorics and Algorithms

Participants: Thomas Dissaux, Frédéric Giroire, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Clément Rambaud.

Title:
Graphs, Optimization, Combinatorics and Algorithms
Duration:
2023 - 2026
Coordinator:
Nicolas Nisse
Partners:
ParGO Research Group, Department of Mathematics, Federal University of Ceará, Fortaleza, Brazil
Summary:
Complementary project of the Inria EA CANOE.

10.2 International research visitors

10.2.1 Visits of international scientists

Pierluigi Crescenzi, professor at the Gran Sasso Science Institute (L'Aquila, Italy), has been visiting the team from 1/04/2023 to 26/05/2023 as an invited professor, funded by the UCA $^{JEDI}$ "Appel à candidatures pour Professeurs Invités UCA 2023".
Jonatan Narboni, Post-Doctoral Researcher, Jagiellonian University (Poland), February $13 - 18$ th 2023.
Jørgen Bang-Jensen, Professor at the University of Southern Denmark, May $22 - 26$ th 2023.
Florian Hörsch, post-doctoral fellow at CISPA Helmholtz Center (Germany), June $12 - 17$ th 2023.
Claudia Linhares Sales, professor at UFC (Fortaleza, Brazil), granted by CAPES-Cofecub project Ma 1004/23 (Graphs, Optimization, Combinatorics and Algorithms). Dec. $3 - 13$ th 2023.
Ana Karolinna Maia, professor at UFC (Fortaleza, Brazil), granted by Inria Associated Team CANOE. Dec. $11 - 22$ th 2023.

10.2.2 Visits to international teams

Research stays abroad

Lucas Picasarri-Arrieta
- SDU, Odense, Denmark. Sep. 25-29, 2023.
Nicolas Nisse and Lucas Picasarri-Arrieta
- UFC, Fortaleza, Brazil (EA CANOE). Nov. 3-29, 2023.

10.3 European initiatives

10.3.1 Horizon Europe

HORIZON-CL4-2022-HUMAN-02-02 dAIEDGE, 2023-2026

Participants: Chuan Xu, Frédéric Giroire.

Program:
HORIZON-CL4-2022-HUMAN-02-02 European Network of AI Excellence Centres: Expanding the European AI lighthouse.
Project acronym:
dAIEDGE
Project title:
A network of excellence for distributed, trustworthy, efficient and scalable AI at the Edge Granting Authority
Duration:
September 2023 - August 2026
Coordinator:
Alain Pagani, DFKI
Other partners:
36 partners from 15 countries.
Summary:

The dAIEDGE Network of Excellence (NoE) seeks to strengthen and support the development of a dynamic European cutting-edge AI ecosystem under the umbrella of the European Lighthouse for AI and to sustain the development of advanced AI.

dAIEDGE fosters the exchange of ideas, concepts, and trends on cutting-edge next generation AI, creating links between ecosystem actors to help both the European Commission (EC) and the European Union (EU) and the peripheral AI constituency identify strategies for future developments in Europe.

Our main objective is to advance Europe's innovation and technology base by developing a comprehensive policy and governance approach to AI in order for the EU to become a world leader in innovation in the data economy and its applications.
Web:
daiedge.eu

10.4 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 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.

Défi Inria Fed-Malin, 2022-2026

Participants: Ilias Driouich, Frédéric Giroire, Chuan Xu.

Project acronym:
Fed-Malin
Project title:
Federated machine Learning over the internet
Duration:
2022 - 2026
Coordinators:
Aurélien Bellet (Inria, EP MAGNET), Giovanni Neglia (Inria, EP NEO)
Inria participants:
Inria project-teams ARGO, COATI, COMETE, EPIONE, MAGNET, MARACAS, NEO, SPIRALS, TRIBE, WIDE
Summary:
In many use-cases of Machine Learning (ML), data is naturally decentralized: medical data is collected and stored by different hospitals, crowdsensed data is generated by personal devices, etc. Federated Learning (FL) has recently emerged as a novel paradigm where a set of entities with local datasets collaboratively train ML models while keeping their data decentralized. Fed-Malin is a research project that spans 10 Inria research teams and aims to push FL research and concrete use-cases through a multidisciplinary consortium involving expertise in ML, distributed systems, privacy and security, networks, and medicine. We propose to address a number of challenges that arise when FL is deployed over the Internet, including privacy & fairness, energy consumption, personalization, and location/time dependencies. Fed-Malin will also contribute to the development of open-source tools for FL experimentation and real-world deployments, and use them for concrete applications in medicine and crowdsensing.

Défi Inria-Hive Alvearium, 2022-2026

Participants: Frédéric Giroire, Stéphane Pérennes.

Project acronym:
Alvearium
Project title:
Large Scale Secure and Reliable Peer-to-Peer Cloud Storage: towards a shared sovereign cloud that respects its users' data
Duration:
2022 - 2026
Coordinator:
Claudia-Lavinia Ignat
Inria participants:
Inria project-teams COAST, COATI, MYRIADS, WIDE
Other partners:
HIVE (www.hivenet.com)
Summary:
The project aims to propose an alternative peer-to-peer cloud which provides both computing and data storage via a peer-to-peer network rather than from a centralized set of data centers. HIVE proposes to exploit the unused capacity of computers and to incentivize users to contribute their computer resources to the network in exchange for similar capacity from the network and/or monetary compensation. By exchanging similar computer resources and network capacity users can benefit from all cloud services. Peers store encrypted fragments of the data of other peers. This proposed peer-to-peer cloud solution addresses users concerns about the privacy of their data and the dependency on centralized cloud providers. In this collaboration with HIVE we will apply our work on replication mechanisms for sharded encrypted data, data placement, Byzantine fault tolerance and security mechanisms in peer-to-peer environments.
Web:
project.inria.fr/alvearium/

PEPR NF (Networks of the Future 2023-2030, 65M€)

Participants: Christelle Caillouet, David Coudert, Frédéric Giroire, Joanna Moulierac.

Project acronym:
NF
Project title:
Networks of the Future
Duration:
2023 - 2030
Coordinators:
CEA (Dmitri Kténas), CNRS (Serge Verdeyme), IMT (Daniel Koffman)
Inria participants:
Inria project-teams AGORA, AIO, COATI, DIANA, DYOGENE, ERMINE, FUN, MARACAS, NEO, RESIST, TRIBE
Summary of PEPR NF:

The 5G network and the networks of the future represent a key issue for French and European industry, society and digital sovereignty. This is why the French government has decided to launch a dedicated national strategy. One of this strategy's priority ambitions is to produce significant public research efforts so the national scientific community contributes fully to making progress that clearly responds to the challenges of 5G and the networks of the future. In this context, the CNRS, the CEA and the Institut Mines-Télécom (ITM) are co-leading the '5G' acceleration PEPR to support upstream research into the development of advanced technologies for 5G and the networks of the future.

Inria is involved into 8 research projects over the 10 supported by the program, with the participation of 11 project-teams of the theme "Networks and Telecommunications" and the coordination of the PC9-Founds.

Coati is involed in PC1 NF-MUST (End-to-end multi domain services management), coordinated by Djamal Zeghlache (IMT), which involves Inria project-teams Coati, DIANA and ERMINE.
Summary of PC1 NF-MUST:

The 5G and 6G end-to-end Multi-Domain Services Management Architecture (NF-MUST) aims at automating production of inter-domain (business and application level) services for 5G, 5G Beyond and 6G networks. This is a challenging and still unrealized evolution of the networks compared with single domain services or pre-established static multi-domain services that are gradually emerging in 5G and Beyond.

Project NF-MUST of the PEPR 5G and Future Networks, focuses mainly on transforming client requests into end-to-end service orderings and on mapping them to resources and network level services (to be) provisioned by the multiple underlying networks. There is a clear evolution of 5 and 6G networks towards the provisioning of services involving multiple players and multiple technologies. Project NF-MUST addresses the related roles and interactions between customers and multiple domains in connection to the other “PEPR 5G and Future Networks” projects, to ensure automated production and operation of multi-domain services across multiple providers. Besides ordering services, NF-MUST will drive the management of the life cycle of the infrastructures” provisioned services and partake in their dynamic and automated adaptation and operation.

NF-MUST operates at the business subsystem (BSS) level and at the service side of the operation subsystem (OSS) level. NF-MUST interacts directly with network services treated by project 2 of the overall program.

PEPR Cloud, 2023-2030

Participants: Frédéric Giroire, Joanna Moulierac.

Project acronym:
Cloud
Project title:
Développement de technologies avancées de cloud
Duration:
2023 - 2030
Coordinators:
CEA, INRIA
Inria participants:
AVALON, COATI, SPIRALS
Summary:

PC CARECLoud - Understanding, improving, reducing the environmental impacts of Cloud Computing.

Cloud computing and its many variations offer users considerable computing and storage capacities. The maturity of virtualization techniques has enabled the emergence of complex virtualized infrastructures, capable of rapidly deploying and reconfiguring virtual and elastic resources in increasingly distributed infrastructures. This resource management, transparent to users, gives the illusion of access to flexible, unlimited and almost immaterial resources. However, the power consumption of these clouds is very real and worrying, as are their overall greenhouse gas (GHG) emissions and the consumption of critical raw materials used in their manufacture. In a context where climate change is becoming more visible and impressive every year, with serious consequences for people and the planet, all sectors (transport, building, agriculture, industry, etc.) must contribute to the effort to reduce GHG emissions. Despite their ability to optimize processes in other sectors (transport, energy, agriculture), clouds are not immune to this observation: the increasing slope of their greenhouse gas emissions must be reversed, otherwise their potential benefits in other sectors will be erased. This is why the CARECloud project (understanding, improving, reducing the environmental impacts of Cloud Computing) aims to drastically reduce the environmental impacts of cloud infrastructures.

Cloud infrastructures are becoming more and more complex: both in width, with more and more distributed infrastructures, whose resources are scattered as close as possible to the user (edge, fog, continuum computing) and in depth, with an increasing software stacking between the hardware and the user's application (operating system, virtual machines, containers, orchestrators, micro- services, etc.) The first objective of the project is to understand how these infrastructures consume energy in order to identify sources of waste and to design new models and metrics to qualify energy efficiency. The second objective focuses on the energy efficiency of cloud infrastructures, i.e., optimizing their consumption during the usage phase. In particular, this involves designing resource allocation and energy lever orchestration strategies: mechanisms that optimize energy consumption (sleep modes, dynamic adjustment of the size of virtual resources, optimization of processor frequency, etc.). Finally, the third objective targets digital sobriety in order to sustainably reduce the environmental impact of clouds. Indeed, current clouds offer high availability and very high fault tolerance, at the cost of significant energy expenditure, particularly due to redundancy and oversizing. This third objective aims to design infrastructures that are more energy and IT resource efficient, resilient to electrical intermittency, adaptable to the production of electricity from renewable energy sources and tolerant of the disconnection of a highly decentralized part of the infrastructure.

PEPR MOBIDEC - Mob Sci-Data Factory project, 2023-2031

Participants: David Coudert.

Project acronym:
MOBIDEC
Project title:
Digitalisation et décarbonation des mobilités
Duration:
2023 - 2030
Coordinators:
IFP Energies nouvelles (IFPEN) and Université Gustave Eiffel (UGE)
Participants Mob Sci-Data Factory:
INRIA (coordinateur), UGE, IFPEN, IGN, CEREMA
Inria participants:
AGORA, ASCII, COATI, FUN, TRIBE
Summary:

The PEPR Data Technology for Mobility in the Territories (MOBIDEC) is in line with France 2030's objective of developing sober, sovereign and resilient mobility, by placing the collection, analysis and processing of mobility data at the heart of its work. It aims to understand and anticipate the mobility behaviors of goods and people, to facilitate the interpretation and processing of data, and to offer decision-making tools to simulate the impact of public policies in advance, or to assess the relevance of a new transport offer.

Coati is involed in project “Mob Sci-Data Factory”, one of the three projects composing the PEPR MOBIDEC. It shares the PEPR's primary goal of contributing to developing more sustainable mobility strategies by providing decision-making support methodology and a digital toolbox fed by appropriately selecting and processing mobility data and by a deeper understanding of the involved transport uses and behaviors in mobility. It aims at clarifying and extracting the elements determining and explaining the characteristics of mobility data, which also raise the following challenging questions: (1) What data and what are their availability, accessibility, quality, and representativeness? (2) Which methods and digital tools are necessary for processing, calibrating, understanding, and enriching data while dealing with missing data and new acquisition ? (3) What are the specifications of the decision-support platform required for standard tools and data research sharing?

Mob Sci-Data Factory will make available in a secure and privacy-compliant cloud-based infrastructure different sources of mobility data together with open-source libraries and methods designed to be unified, modular, and interoperable from conception. Mob Sci-Dat Factory outcomes will facilitate data sovereignty and open-source development interoperability across multiple scientific actors in France, while accelerating research focused on mobility by offering privacy-compliant and secure data accessibility.

10.4.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/pole-rescom). In particular, Christelle Caillouet is co-chair of this working group since July 2022.

We are also involved in the working group "Energy" of GDR RSD (gdr-rsd.fr/gt-energie). 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" (gtgraphes.labri.fr/) and Complexité et algorithmes (CoA) www.gdr-im.fr/les-gt/gt-coa/ of GDR IM, CNRS. (gtgraphes.labri.fr/). In particular, Frédéric Havet is member of the steering committee of the GT Graphes and Nicolas Nisse is member of the steering committee of the GT CoA.

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/).

11 Dissemination

11.1 Promoting scientific activities

11.1.1 Scientific events: Steering Committees

David Coudert :
- member of the steering committee of the Symposium on Experimental Algorithms, since September 2022.
Emanuele Natale :
- member of the steering committee of the Symposium on Experimental Algorithms, since September 2022.
Nicolas Nisse :
- member of the steering committee of the Workshop on GRAph Searching, Theory and Applications, since 2014.

11.1.2 Scientific events: organisation

General chair, scientific chair

Christelle Caillouet :
- Organizing chair of the annual conferences CoRes and AlgoTel of the GDR RSD located in Cargèse, France, May 22-26 2023. coresalgotel2023.i3s.univ-cotedazur.fr
Nicolas Nisse :
- Organizing chair and scientific chair of the 11th Workshop on GRAph Searching, Theory and Applications, Bertinoro, Italy, October 22-27, 2023 grasta23.bici.events/home.

Member of the organizing committees

David Coudert :
- UCA-Majulab Workshop 2023: quantum technologies & photonics, Nice, France, June 19-21, 2023. www-sop.inria.fr/coati/events/ucamajulab2023/

11.1.3 Scientific events: selection

Chair of conference program committees

Christelle Caillouet :
- Co-PC chair with Nancy Perrot and Eric Gourdin (Orange Labs) of the session "Optimisation dans les Réseaux Telecom" at the conference Roadef 2023.

Member of the conference program committees

Christelle Caillouet :
- AlgoTel : 25èmes Rencontres francophones sur les aspects algorithmiques des télécommunications, Cargèse, France, 22-26 May 2023;
- Wisarn : 16th International Workshop on WIreless Sensing and Actuating Robotic Networks (in conjunction with IEEE INFOCOM 2023), New-York, USA, 17-20 May 2023;
- Wimob : 19th International Conference on Wireless and Mobile Computing, Networking and Communications, Montreal, Canada, 21-23 June 2023;
- VTC-Spring : IEEE 97th Vehicular Technology Conference, Florence, Italy, 20-23 June 2023;
- ITC35 : 35th International Telecongress Conference, Turin, Italy, 3-5 October 2023.
David Coudert:
- ATMOS: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Amsterdam, Netherlands, September 7-8, 2023;
- ESA - track B: European Symposium on Algorithms, Amsterdam, Netherlands, September 4-6, 2023;
- IEEE ICC: IEEE International Conference on Communications, Rome, Italy, May 28 -June 1st, 2023;
- IEEE Globecom: IEEE Global Communications Conference, Kuala Lumpur, Malaysia, December 4-8, 2023;
- ONDM: Conference on Optical Network Design and Management, Coimbra, Portugal, May 8-11 2023.
Frédéric Havet :
- LAGOS : XII Latin-American Algorithms, Graphs and Optimization Symposium, Huatulco, Mexico, September 18-22th, 2023;
- JGA : 25èmes Journées Graphes et Algoritmes, Lyon, France, November 12-14th, 2023.
Emanuele Natale:
- NeurIPS: Thirty-seventh Conference on Neural Information Processing Systems, New Orleans, LA, USA, December 10-16, 2023;
- AAAI: The 38th Annual AAAI Conference on Artificial Intelligence, Vancouver, Canada, February 20-27 2024;
- UAI: 39th Conference on Uncertainty in Artificial Intelligence, Pittsburgh, PA, USA, 31 July - 4 August 2023 (identified as Top Reviewer by the PC chairs);
- AAAI: The 37th Annual AAAI Conference on Artificial Intelligence, Washington, DC, USA, February 7-14 2023;
- JuliaCon: The Julia Programming Language Conference, Cambridge, USA, July 25-29 2023.
Nicolas Nisse :
- AlgoTel : 25èmes Rencontres francophones sur les aspects algorithmiques des télécommunications, Cargèse, France, 22-26 May 2023;
- LAGOS : XII Latin-American Algorithms, Graphs and Optimization Symposium, Huatulco, Mexico, September 18-22th, 2023.
Chuan Xu :
- Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities Workshop at ICML 2023, Hawaii, USA, July 28, 2023 .

11.1.4 Journal

Member of the editorial boards

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);
- Innovations in Graph Theory
Emanuele Natale
- The WikiJournal of Science (Wikimedia Foundation).
Nicolas Nisse :
- Discrete Applied Mathematics (Elsevier).

11.1.5 Invited talks

Chuan Xu
- Passive attacks for federated learning. Days on Distributed Learning, GDR RSD Summer School on Distributed Learning, September 21th-22th, Lyon, France
Nicolas Nisse
- Deciding the Erdös-Pósa property in 3-connected digraphs. 2nd Fortaleza Workshop on Combinatorics (ForWorC), 6-10th November 2023, Fortaleza, Brazil

11.1.6 Leadership within the scientific community

Christelle Caillouet :
- Co-chair of Pôle RESCOM of GDR RSD of CNRS since July 2022.
David Coudert :
- Member of the steering committee of the Institut Fédératif Quantique Azuréen (QuantAzur) at Université Côte d'Azur till June 2023;
- Member of the steering committee of seminar Forum Numerica of Academy 1 RISE of UCA $^{JEDI}$ since 2018;
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".
Nicolas Nisse :
- Member of the steering committee of GT CoA of the GDR IM of CNRS since 2018;

11.1.7 Scientific expertise

Jean-Claude Bermond :
- Expert for DRTT-MESR Crédit impôt recherche (CIR et agréments).
David Coudert :
- Expert for ANR;
- Expert for the Emergence 2023-2024 call of Sorbonne Université.
Emanuele Natale :
- Member of the ST6 Expert Panel (Computer science and informatics) of the National Science Centre of Poland, 2023.
Nicolas Nisse
- Expert for EUTOPIA Science and Innovation Program;
- Expert for ECOS SUD CHILI 2023.

11.1.8 Research administration

Christelle Caillouet
- Elected member of Conseil de Laboratoire I3S since 2017;
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 :
- Head of Science of the Inria Centre at Université Côte d'Azur, since September 2022;
- Member of the “Bureau du comité des équipe-projets” of Inria research center Sophia Antipolis - Méditerranée since 2018;
- Member of the Inria Evaluation Committee, since September 2022;
- Member of the Inria committee for researchers promotions (CRHC, CRHC-8, DR1, DRCE, DRCE-2), 2023;
- Member of the Inria selection committee for Senior Researchers (DR2), 2023.
Frédéric Giroire :
- Head of COMRED team of I3S laboratory, since April 2022;
- In charge of the internships of stream UbiNet of Master 2 IFI, Université Côte d'Azur.
Frédéric Havet
- Coordinator of ANR project Digraphs;
- Co-head of Terra Numerica.
Joanna Moulierac:
- Member of the CA of SPECIF-CAMPUS (Société Professionnelle des Enseignants et Chercheurs en Informatique de France);
- Member of the I3S CO2 group since 2019 (www.i3s.unice.fr/co2/);
- Member of the CSPT ( Comité Scientifique, Pédagogique et Technique) Terra Numerica, since 2022.
Emanuele Natale:
- External member of University of Rome Tor Vergata's PhD School in Data Science (Italy).
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;
- Nominated member for Inria at the board of doctoral school STIC, since September 2022;
- Member of the “Comité de Suivi Doctoral” of Inria, since September 2022;
- Member of the CSPT Terra Numerica, since 2020.
Luc Hogie
- Elected member of Conseil de Laboratoire I3S.

11.2 Teaching - Supervision - Juries

11.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.
Christelle Caillouet :
- Member of the “Conseil de Département Informatique” of IUT Nice Côte d'Azur (since September 2022).
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 :
- Member of the “Conseil de Département Informatique” of IUT Nice Côte d'Azur (since September 2017).
Michel Syska :
- Head of the MIAGE (IT methods applied to business management) Master’s degree MBDS (Mobiquity, Big Data and Systems integration), of Université Côte d'Azur (since September 2022);
- Co 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.

11.2.2 Teaching

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

BUT: Julien Bensmail, Recherche opérationnelle, 90h ETD, Level L2, Département QLIO of IUT, Université Côte d'Azur, France;
BUT: Julien Bensmail, Algorithmique et programmation avancées, 64h ETD, Level L2, Département QLIO of IUT, Université Côte d'Azur, France;
BUT: Thomas Dissaux, Communication et fonctionnement bas niveau, 20h ETD, Level L1, Département Informatique of IUT, Université Côte d’Azur, France;
BUT: Thomas Dissaux, Introduction aux services réseaux, 14h ETD, Level L1, Département Informatique of IUT, Université Côte d’Azur, France;
BUT: Thomas Dissaux, Initiation au développement, 64h ETD, Level L1, Département Informatique of IUT, Université Côte d’Azur, France;
BUT: Luc Hogie, System programming, 24h ETD, Level L2, IUT, Université Côte d'Azur, France;
BUT: Christelle Caillouet, Automates et langages, 12h ETD, Level L2, IUT, Université Côte d'Azur, France;
BUT: Christelle Caillouet, Programmation orientée objet, 48h ETD, Level L1, IUT, Université Côte d'Azur, France;
BUT: Christelle Caillouet, Méthodes d'optimisation pour l'aide à la décision, 21h ETD, Level L3, IUT, Université Côte d'Azur, France;
BUT: Lucas Picasarri-Arrieta, Automates et langages, 12h ETD, Level L2, IUT, Université Côte d'Azur, France;
BUT: Lucas Picasarri-Arrieta, Introduction à la programmation, 52h ETD, Level L1, IUT, Université Côte d'Azur, France;
BUT: Lucas Picasarri-Arrieta, Méthodes d'optimisation pour l'aide à la décision, 12h ETD, Level L1, IUT, Université Côte d'Azur, France;
BUT: Joanna Moulierac, Introduction aux Réseaux, 56h ETD, Level L1, IUT, Université Côte d'Azur, France;
BUT: Joanna Moulierac, Réseaux avancés, 30h ETD, Level L2, IUT, Université Côte d'Azur, France;
PeiP: Joanna Moulierac, Programmation Objet, 30h ETD, Level L1, Polytech, Université Côte d'Azur, France;
LP: Julien Bensmail, Sécurité des échanges de données inter-entreprises, 30h ETD, Level LP, LP MPL of IUT, Université Côte d'Azur, France;
LP: Joanna Moulierac, Programmation C#, 30h ETD, Level L3, IUT, Université Côte d'Azur, France;
Licence: Michel Syska, Algorithmics, 33h ETD, Level L3, parcours IA Science & Technologie - Université Côte d’Azur, France;
Licence: Michel Syska, Heuristic search, 21h ETD, Level L3, parcours IA Science & Technologie - Université Côte d’Azur, France;
Licence: Chuan Xu, Programmation fonctionnelle, 36h ETD, Level L3, Université Côte d’Azur, France;
Licence: Chuan Xu, Python pour l'IA, 30h ETD, Level L3, MIAGE IA2 - Université Côte d’Azur, France;
Licence: Clément Rambaud, Informatique Théorique, 20h ETD, MAM3, Polytech Nice Sophia Antipolis, France;
Master: Christelle Caillouet, Introduction Algorithmic and Programming, 60h ETD, MAM3, Polytech Nice Sophia Antipolis, France;
Master: Alexandre Caminada, Radio location systems, 20h ETD, Master 2 (in english), Polytech Nice Sophia Antipolis, 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 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, 34.5 h 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: Michel Syska, Databases for big data, 20h ETD, M1 MIAGE - Université Côte d’Azur, France;
Master: Michel Syska, Cloud computing, 45h ETD, M2 MIAGE MBDS - Université Côte d’Azur, France.

11.2.3 Supervision

PhD thesis

PhD in progress: Tiago da Silva Barros, Joint Training Design and Network Resource Allocation for Distributed Machine Learning , since October 2022. Co-supervisors: Ramon Aparicio and Frederic Giroire;
PhD in progress: Ilias Driouich, Privacy-preserving algorithms for cross-device federated learning. Co-supervisors: Frédéric Giroire and Chuan Xu. CIFRE grant with Amadeus;
PhD in progress: Henrique Lovisi Ennes, Calcul quantique en topologie, since October 2023. Co-supervisors: Clément Maria (DataShape) and Nicolas Nisse;
PhD in progress: Lucas Picasarri-Arrieta , Digraph colouring, since October 2021. Supervisor: Frédéric Havet;
PhD in progress: Clément Rambaud, Colourong digraphs, since September 2023. Supervisor: Frédéric Havet;
PhD in progress: Aurora Rossi, Algorithmic aspects and random network models for temporal brain networks, since October 2022. Supervisor: David Coudert;
PhD defended September 13 2023: Arthur Carvalho Walraven da Cunha, Pruning random structures. Supervisor: Emanuele Natale;
PhD defended September 21 2023: Igor Dias da Silva, Optimisation of UAVs deployment and coordination for exploration and monitoring applications 57. Co-supervisors: Christelle Caillouet and David Coudert;
PhD defended September 25 2023: Thomas Dissaux, Graph decompositions: Treelength and pursuit-evasion games 58. Supervisor: Nicolas Nisse.

Internships

License (tutorship): Andranik Arakelov, Kishan Turpin, Adrien Escoubeyrou, Development of games for Terra Numerica, M2 IoT CPS, Université Côte d'Azur, France, from October 2023 until March 2024. Supervisor: Luc Hogie;
Licence: Teiki Rigaud, Problème d'ordonnancement pour la technologie LoRa, L3 ENS PSL, June-July, 2023. Supervisors: Christelle Caillouet, Frédéric Havet, Lucas Picasarri-Arrieta;
Licence: Justine Cauvi, Bornes inférieures pour la largeur de coupe des graphes, L3 ENS Lyon, June-July, 2023. Supervisor: David Coudert;
Licence: Maël Clergue, Scientific Machine Learning for World Dynamics Modeling, ENS Lyon, June-July, 2023. Supervisor: Emanuele Natale;
Master 1 (tutorship): Dimitri Morelle, Differential privacy and byzantine resilience in federated learning, M1 Computer Science, Digital Systems for Humans (DS4H) Graduate school - Université Côte d'Azur, France, from October 2023 until December 2023. Supervisor: Chuan Xu;
Master 1: Lilian Fortas, Pathlength of chordal graphs, année de césure Centrale-Supélec (entre 2 et $3^{m e}$ année), from September 2023 to February 24. Supervisor: Nicolas Nisse;
Master 2 (TER): Valentin Mascaro, Sadmi Joudet, On the Use of Digital Twins for the Decentralized Management of Large Multihop Mobile Networks, M2 IoT CPS, Université Côte d'Azur, France, from October 2023 until March 2024. Supervisor: Luc Hogie;
Master 2 (TER): Valentin Mascaro, Sadmi Joudet, On the Use of Digital Twins for the Decentralized Management of Large Multihop Mobile Networks, M2 IoT CPS, Université Côte d'Azur, France, from October 2023 until March 2024. Supervisor: Luc Hogie;
Master 2: Pietro Ventrella, Study of Large Distributed Storage Systems, Ubinet international track, Université Côte d'Azur, France, from October 2023 until December 2023. Supervisors: Frédéric Giroire and Stéphane Pérennes;
Master 2 (TER): Fatima Laaziz, Privacy on-demand and Security preserving Federated Generative Networks or Models, Ubinet, Université Côte d'Azur, France, from October 2023 until December 2023. Supervisors: Chuan Xu and Frédéric Giroire;
Master 2 (TER): Sohaib Idalin, Differential privacy and byzantine resilience in federated learning, Ubinet, Université Côte d'Azur, France, from October 2023 until December 2023. Supervisors: Chuan Xu and Giovanni Neglia.

11.2.4 Juries

Christelle Caillouet:
- Member of the Comité de suivi individuel of Masoud Taghavian, IMT Atlantique, June 13, 2023;
- Member of the PhD committee of Nina Santi, FUN team Inria Lille, 19 December 2023;
- Member of the PhD committee of Alessandro Aimi, CNAM Paris, 19 September 2023.
David Coudert:
- Member of the Comité de suivi individuel of Zahraa Al Atar, IMT Atlantique and Université de Rennes 1, May 5, 2023;
- Member of the PhD committee of Fabrice Lécuyer on Ordering nodes to scale to large real-world networks, Sorbonne Université, LIP6, Paris, France, July 6, 2023.
Frédéric Giroire:
- President of the PhD committee of Othmane Marfoq on Tackling Heterogeneity in Federated Learning Systems, Université Côte d’Azur, Neo team Inria, Sophia Antipolis, France, December 7, 2023;
- President of the PhD committee of François Doré on Drawing graphs on surfaces of null and higher genus, Université Côte d’Azur, Inria, Sophia Antipolis, France, December 11, 2023;
- Member of the PhD committee of Chen Dang on Heuristics Learning for Solving Network Optimization Problems, Université Paris Dauphine-PSL, Paris, France, December 8, 2023;
- Member of the PhD committee of Arthur C. W. da Cunha on Pruning random structures, Université Côte d’Azur, Coati team Inria, Sophia Antipolis, France, September 13, 2023;
- Member of the Comité de suivi individuel of Pierre-Marie Lechevalier, IMT Atlantique and Université de Rennes 1, May 2, 2023;
- Member of the Comité de suivi individuel of Angelo Rodio, Université Côte d’Azur, Neo team Inria, Sophia Antipolis, France, June 16, 2023;
- Member of the Comité de suivi individuel of Younes Ben Mazzianne, Université Côte d’Azur, Neo team Inria, Sophia Antipolis, France, May 16, 2023;
- Member of the Comité de suivi individuel of Aymeric Picard Marchetto, Université Côte d’Azur, I3S, Sophia Antipolis, France, June 30, 2023.
Frédéric Havet:
- Member of the PhD committee of Giannos Stamoulis, Université de Montpellier, France, December 12, 2023;
- Reviewer of the PhD committee of Rémi Pellerin, ENS Lyon, France, December 11, 2023;
- Member of the PhD committee of Jonas Costa Ferreira da Silva, Universidade Federal do Ceara, Brasil, May 25, 2023;
- Member of the Comité de suivi individuel of François Doré, Université Côte d’Azur, I3S, Sophia Antipolis, France, July 12, 2023;
- Member of the Comité de suivi individuel of Nacim Oijid, Université Lyon 1, France, May 12, 2023.
Joanna Moulierac:
- Member of the Comité de suivi individuel of Killian Castillon, Université Côte d’Azur, France, May 12, 2023.
Emanuele Natale:
- Member of Prokopchik Konstantin's PhD jury. Date of defense: March 24th 2023. Institution: GSSI (L'Aquila, Italy). Thesis title: Hypergraph-based Methods for Semi-Supervised Learning.
Nicolas Nisse
- Member of the Comité de suivi individuel of Evangelos Protopapas, LIRMM, Université Montpellier, France, September 21, 2023.

11.3 Popularization

Participants: Caroline Brosse, Michel Cosnard, Frédéric Giroire, Frédéric Havet, Joanna Moulierac, Nicolas Nisse, Lucas Picasarri-Arrieta, Stéphane Pérennes, Clément Rambaud, Michel Syska.

Coati is deeply involved in Terra Numerica. Its members are very active in content creation, dissemination to the public, training of teaching or facilitating staff, and project governance.

Frédéric Havet and Nicolas Nisse are also involved in the ANR project ASMODEE (Analyse et conception de situations de médiation en informatique débranchée) headed by the LIRIS laboratory.

11.3.1 Internal or external Inria responsibilities

Frédéric Havet is co-head of Terra Numerica and one of the responsible of the “Comité Scientifique, Pédagogique et Technique” ; Nicolas Nisse is a member of this committee ; Joanna Moulierac is the referent of Terra Numerica for higher education ; Luc Hogie is in charge of hardware and software development.

Frédéric Havet is member of the editorial board of 1024, le bulletin de la SIF (Société Informatique de France, in which he draws cartoons to illustrate some articles.

11.3.2 Articles and contents

Press articles related to Terra Numerica can be found at terra-numerica.org/presse/. Members of Coati have contributed to several of them.

11.3.3 Education

Most of the members of Coati are involved in Terra Numerica. During the year 2023, more than 300 events held, Terra Numerica has been visited by 290 classes (about 8000 primary school/college/highschool student, for 2 hours in average). We have trained about 360 persons (including 250 teachers) and touched more than 15000 people during events such as Fête de la science, etc.

11.3.4 Interventions

Many members of Coati (C. Brosse, M. Cosnard, F. Giroire, F. Havet, J. Moulierac, N. Nisse, L. Picasarri-Arrieta, S. Pérennes, C. Rambaud, M. Syska) participated some general audience science fairs, such as the Fête de la science in October 2024 (we were present on the “Village des Sciences” in Antibes-Juan-les-Pins, Valbonne, Villeneuve-Loubet, Vinon-sur Verdon) or some stages of the Science Tour Terra Numerica (20 days in several places : Digne-les-Bains, Forcalquier, Manosque, Aups, La Seyne sur Mer, Brignoles, Draguignan, Salernes, Roquebillière, Saint Martin de Vésubie, Breil sur Roya, Tende. They also occasionally act as scientific facilitator at Terra Numerica.

Frédéric Havet also gave general audience conferences in several cities (Bonson, Brignoles, Draguigan, Falicon, Menton, Rians, Vinon-sur-Verdon) as well as in for Esope 21, Science pour Tous 06, and Terra Numerica.

12 Scientific production

12.1 Major publications

1 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 2020HAL
2 inproceedingsJ.Julien Bensmail, V.Victor Campos, A. K.Ana Karolinna Maia, N.Nicolas Nisse and A.Ana Silva. Deciding the Erdős-Pósa property in 3-connected digraphs ⋆.WG 2023 - 49th International Workshop on Graph-Theoretic Concepts in Computer ScienceLNCSFribourg (CH), SwitzerlandJune 2023HAL
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-263HAL DOI
4 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-125HAL
5 articleN.Nicolas Bousquet, F.Frédéric Havet, N.Nicolas Nisse, L.Lucas Picasarri-Arrieta and A.Amadeus Reinald. Digraph redicolouring.European Journal of Combinatorics116February 2024, 103876HAL DOI
6 articleC.Christelle Caillouet, F.Frédéric Giroire and T.Tahiry Razafindralambo. Efficient Data Collection and Tracking with Flying Drones.Ad Hoc Networks89C2019, 35-46HAL DOI
7 articleD.David Coudert, G.Guillaume Ducoffe and N.Nicolas Nisse. To Approximate Treewidth, Use Treelength!SIAM Journal on Discrete Mathematics3032016, 13HAL DOI
8 articleD.David Coudert, G.Guillaume Ducoffe and A.Alexandru Popa. P-FPT algorithms for bounded clique-width graphs.ACM Transactions on Algorithms153June 2019, 1-57HAL DOI
9 inproceedingsA.Arthur da Cunha, E.Emanuele Natale and L.Laurent Viennot. Proving the Strong Lottery Ticket Hypothesis for Convolutional Neural Networks.ICLR 2022 - 10th International Conference on Learning RepresentationsVirtual, FranceApril 2022HAL
10 articleF.François Dross and F.Frédéric Havet. On the unavoidability of oriented trees.Journal of Combinatorial Theory, Series B151November 2021, 83-110HAL DOI
11 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-233HAL DOI
12 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--140HAL DOI
13 patentL.Luc Hogie, M.Michel Syska and N.Nicolas Chleq. BigGraphs: distributed graph computing.IDDN.FR.001.410005.000.S.P.2015.000.31235FranceSeptember 2016HAL
14 inproceedingsH.Hicham Lesfari and F.Frédéric Giroire. Nadege: When Graph Kernels meet Network Anomaly Detection.IEEE International Conference on Computer Communications (INFOCOM)London, United KingdomMay 2022HAL
15 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-207HAL DOI

12.2 Publications of the year

International journals

16 articleA.Ali Al Zoobi, D.David Coudert and N.Nicolas Nisse. Finding the k Shortest Simple Paths: Time and Space trade-offs.ACM Journal of Experimental Algorithmics28October 2023, 23HAL DOI back to text
17 articleJ.Julio Araujo, J.Julien Bensmail, V.Victor Campos, F.Frédéric Havet, A. K.A. Karolinna Maia, N.Nicolas Nisse and A.Ana Silva. On Finding the Best and Worst Orientations for the Metric Dimension.Algorithmica8510October 2023, 2962-3002HAL DOI back to text
18 articleF.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.European Journal of CombinatoricsSeptember 2023, 18HAL DOI back to text
19 articleJ.Julien Bensmail. A notion of vertex equitability for proper labellings.Discrete Applied Mathematics3462024, 228-247HAL back to text
20 articleJ.Julien Bensmail, T.Tapas Das, D.Dimitri Lajou, S.Soumen Nandi and S.Sagnik Sen. On the pushable chromatic number of various types of grids.Discrete Applied Mathematics3292023, 140-154HAL DOI back to text
21 articleJ.Julien Bensmail, F.Foivos Fioravantes, F.Fionn Mc Inerney, N.Nicolas Nisse and N.Nacim Oijid. The Maker-Breaker Largest Connected Subgraph Game.Theoretical Computer Science9432023, 102-120HAL DOI back to text back to text
22 articleJ.Julien Bensmail, H.Hervé Hocquard and D.Dimitri Lajou. On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs.Theoretical Computer Science9392023, 105-118HAL DOI back to text
23 articleJ.Julien Bensmail, H.Hervé Hocquard, D.Dimitri Lajou and É.Éric Sopena. A proof of the Multiplicative 1-2-3 Conjecture.Combinatorica432023, 37-55HAL DOI back to text
24 articleJ.Julien Bensmail, H.Hervé Hocquard and P.-M.Pierre-Marie Marcille. On inducing degenerate sums through 2-labellings.Graphs and Combinatorics2024HAL back to text
25 articleJ.Julien Bensmail. Maximising 1's through Proper Labellings.Discussiones Mathematicae Graph Theory2023HAL back to text
26 articleJ.Julien Bensmail. Some Properties of Minimal Arbitrarily Partitionable Graphs.The Australasian Journal of Combinatorics8612023, 149-168HAL back to text
27 articleJ.-C.Jean-Claude Bermond, T.Takako Kodate and J.Joseph Yu. Gossiping with interference in radio ring networks.Discrete Mathematics and Theoretical Computer Science2522023, #5HAL DOI back to text
28 articleS.Stéphane Bessy, J.Johannes Pardey, L.Lucas Picasarri-Arrieta and D.Dieter Rautenbach. Unbalanced Spanning Subgraphs in Edge Labeled Complete Graphs.The Electronic Journal of Combinatorics3012023, 1-35HAL DOI back to text
29 articleN.Nicolas Bousquet, F.Frédéric Havet, N.Nicolas Nisse, L.Lucas Picasarri-Arrieta and A.Amadeus Reinald. Digraph redicolouring.European Journal of Combinatorics116February 2024, 103876HAL DOI back to text
30 articleC.Cláudio Carvalho, J.Jonas Costa, R.Raul Lopes, A. K.Ana Karolinna Maia, N.Nicolas Nisse and C. L.Cláudia Linhares Sales. From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows.Discrete Mathematics and Theoretical Computer Sciencevol. 25:110May 2023, 15HAL DOI back to text
31 articleT.Thomas Dissaux, G.Guillaume Ducoffe, N.Nicolas Nisse and S.Simon Nivelle. Treelength of series–parallel graphs.Discrete Applied Mathematics341December 2023, 16-30HAL DOI back to text
32 articleF.Frédéric Giroire, S.Stéphane Pérennes and T.Thibaud Trolliet. A Random Growth Model with any Real or Theoretical Degree Distribution.Theoretical Computer Science940Part AJanuary 2023, 36-51HAL DOI back to text
33 articleM.Martin Heusse, C.Christelle Caillouet and A.Andrzej Duda. Performance of Unslotted ALOHA with Capture and Multiple Collisions in LoRaWAN.IEEE Internet of Things Journal1020October 2023, 17824 - 17838HAL DOI back to text
34 articleL.Lucas Picasarri-Arrieta. Strengthening the Directed Brooks' Theorem for oriented graphs and consequences on digraph redicolouring.Journal of Graph TheoryDecember 2023HAL DOI back to text

International peer-reviewed conferences

35 inproceedingsR. A.Redha A. Alliche, T.Tiago da Silva Barros, R.Ramon Aparicio-Pardo and L.Lucile Sassatelli. prisma-v2: Extension to Cloud Overlay Networks.ICTON 2023 - 23rd International Conference on Transparent Optical NetworksBucarest, RomaniaIEEEJuly 2023HAL DOI back to text
36 inproceedingsJ.Julio Araujo, F.Frédéric Havet, C. L.C. Linhares Sales, K.Karol Suchan and N.Nicolas Nisse. Semi-proper orientations of dense graphs.LAGOS 2023 6 XII Latin-American Algorithms, Graphs and Optimization Symposium223Huatulco, Mexico2023, 231-240HAL DOI back to text
37 inproceedingsJ.Julien Bensmail, V.Victor Campos, A. K.Ana Karolinna Maia, N.Nicolas Nisse and A.Ana Silva. Deciding the Erdős-Pósa property in 3-connected digraphs.WG 2023 - 49th International Workshop on Graph-Theoretic Concepts in Computer ScienceLNCSFribourg (CH), SwitzerlandJune 2023HAL back to text
38 inproceedingsJ.Julien Bensmail, H.Hervé Hocquard and P.-M.Pierre-Marie Marcille. The Weak (2,2)-Labelling Problem for graphs with forbidden induced structures.Lecture Notes in Computer ScienceCALDAM 2023 - 9th Annual International Conference on Algorithms and Discrete Applied MathematicsGandhinagar, IndiaSpringerFebruary 2023HAL DOI back to text
39 inproceedingsA.Arthur Carvalho Walraven da Cunha, E.Emanuele Natale and L.Laurent Viennot. Neural Network Information Leakage through Hidden Learning.Communications in Computer and Information Science (CCIS) seriesOLA2023 - International Conference on Optimization and Learning1824Communications in Computer and Information ScienceMalaga, SpainSpringer Nature SwitzerlandFebruary 2023, 117-128HAL DOI back to text
40 inproceedingsA.Arthur Carvalho Walraven da Cunha, F.Francesco d'Amore and E.Emanuele Natale. Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets.37th Conference on Neural Information Processing Systems (NeurIPS 2023)New Orleans, United StatesDecember 2023HAL back to text
41 inproceedingsA.Arthur da Cunha, D.Damien Rivet, E.Emanuele Natale and A.Aurora Rossi. Une implémentation GPU de la méthode de recherche approximative FlyHash.CAID 2023 - 5e Conference on Artificial Intelligence for DefenseActes de la conférence CAID 2023Rennes, FranceNovember 2023HAL back to text
42 inproceedingsA. C.Arthur Carvalho Walraven da Cunha, F.Francesco d'Amore, F.Frédéric Giroire, H.Hicham Lesfari, E.Emanuele Natale and L.Laurent Viennot. Revisiting the Random Subset Sum problem.31st Annual European Symposium on Algorithms (ESA 2023)31st Annual European Symposium on Algorithms (ESA 2023)Amsterdam, NetherlandsSchloss Dagstuhl - Leibniz-Zentrum für InformatikSeptember 2023, 37:1--37:11HAL DOI back to text
43 inproceedingsC.Cinzia Di Giusto, D.Davide Ferré, E.Etienne Lozes and N.Nicolas Nisse. Weakly Synchronous Systems with Three Machines Are Turing Powerful.Lecture Notes in Computer ScienceRP 2023 - 17th International Conference on Reachability ProblemsLNCS-14235Reachability Problems 17th International Conference, RP 2023, Nice, France, October 11–13, 2023, ProceedingsNice, FranceSpringer Nature SwitzerlandOctober 2023, 28-41HAL DOI back to text
44 inproceedingsT.Thomas Dissaux, F.Foivos Fioravantes, H.Harmender Gahlawat and N.Nicolas Nisse. Recontamination Helps a Lot to Hunt a Rabbit.Leibniz International Proceedings in Informatics (ISSN 1868-8969)MFCS 2023 - 48th International Symposium on Mathematical Foundations of Computer ScienceLIPICS-27248th International Symposium on Mathematical Foundations of Computer ScienceBordeaux, FranceSchloss Dagstuhl - Leibniz-Zentrum für Informatik2023, 42:1--42:14HAL DOI back to text
45 inproceedingsJ.Julien Duron, F.Frédéric Havet, F.Florian Hörsch and C.Clément Rambaud. On the minimum number of inversions to make a digraph k-(arc-)strong.MUNI journalsEUROCOMB 2023 - European Conference on Combinatorics, Graph Theory and ApplicationsProceedings of the 12th European Conference on Combinatorics, Graph Theory and ApplicationsPrague, Czech RepublicMasaryk University Press; Masaryk University PressAugust 2023, 386-392HAL DOI back to text
46 inproceedingsF.Frédéric Giroire, N.Nicolas Nisse, K.Kostiantyn Ohulchanskyi, M.Małgorzata Sulkowska and T.Thibaud Trolliet. Preferential attachment hypergraph with vertex deactivation.IEEE Computer society digital libraryMASCOTS 2023 - 31st International Symposium on the Modeling, Analysis, and Simulation of Computer and Telecommunication Systems20232023 31th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)New York, United StatesOctober 2023HAL back to text
47 inproceedingsF.Frédéric Havet, L.Lucas Picasarri-Arrieta and C.Clément Rambaud. On the Minimum Number of Arcs in 4-Dicritical Oriented Graphs.Lecture Notes in Computer ScienceWG 2023 - International Workshop on Graph-Theoretic Concepts in Computer ScienceLNCS-14093Graph-Theoretic Concepts in Computer Science 49th International Workshop, WG 2023, Fribourg, Switzerland, June 28–30, 2023, Revised Selected PapersFribourg, SwitzerlandSpringerJune 2023, 376–387HAL DOI back to text
48 inproceedingsM.Martin Heusse and C.Christelle Caillouet. Adjusting the Redundancy Level of LoRaWAN transmissions.CoRes 2023 - 8èmes Rencontres Francophones sur la Conception de protocoles, l'évaluation de performances et l'expérimentation de Réseaux de communicationCoRes 2023 - 8èmes Rencontres Francophones sur la Conception de protocoles, l'évaluation de performances et l'expérimentation de Réseaux de communicationCargese, FranceMay 2023HAL back to text
49 inproceedingsL.Luc Hogie. A Decentralized Web Service Infrastructure for the Interoperability of Applications in Multihop Dynamic Networks.CIoT 2023 - 6th Conference on Cloud and Internet of ThingsLisbon, PortugalIEEEMarch 2023, 211-218HAL DOI back to text
50 inproceedingsZ.Zhejiayu Ma, F.Frédéric Giroire, G.Guillaume Urvoy-Keller and S.Soufiane Roubia. Q-learning for Waiting Time Control in CDN/V2V Live streaming.2023 IFIP Networking Conference (IFIP Networking)20232023 IFIP Networking Conference (IFIP Networking)Barcelona, SpainIEEEJune 2023, 1-9HAL DOI back to text
51 inproceedingsL.Lucas Picasarri-Arrieta. Strengthening the Directed Brooks' Theorem for oriented graphs and consequences on digraph redicolouring.Eurocomb 2023 - 12th European Conference on Combinatorics, Graph Theory and ApplicationsEurocomb 2023 - 12th European Conference on Combinatorics, Graph Theory and ApplicationsPrague, Czech RepublicMasaryk University Press2023, 760-765HAL DOI back to text
52 inproceedingsA.Aurora Rossi, S.Samuel Deslauriers-Gauthier and E.Emanuele Natale. Temporal Hyperbolic Graphs as Null Models for Brain Dynamics.Temporal Hyperbolic Graphs as Null Models for Brain DynamicsThe 12th International Conference on Complex Networks and their Applications - CNA 2023Menton, FranceNovember 2023HAL back to text
53 inproceedingsF.Fatemeh Tabatabaeimehr, L.Luis Velasco, M.Marc Ruiz, H.Hamzeh Khalili and R.Ramon Aparicio-Pardo. Dynamic Traffic Prediction Model Retraining for Autonomous Network Operation.ICTON 2023 - 23rd International Conference on Transparent Optical NetworksBucharest, RomaniaIEEEJuly 2023HAL DOI

National peer-reviewed Conferences

54 inproceedingsJ.-C.Jean-Claude Bermond, M.Michel Cosnard, D.David Coudert and F.Frédéric Havet. Groupage sur le chemin pour borner la largeur de coupe.AlgoTel 2023 - 25èmes Rencontres Francophones sur les Aspects Algorithmiques des TélécommunicationsCargese, France2023, 4HAL back to text
55 inproceedingsI.Igor Dias da Silva, Y.Yann Busnel and C.Christelle Caillouet. Optimisation de plan de vol de drones autonomes pour une recharge rapide de capteurs.AlgoTel 2023 - 25èmes Rencontres Francophones sur les Aspects Algorithmiques des TélécommunicationsAlgoTel 2023 - 25èmes Rencontres Francophones sur les Aspects Algorithmiques des TélécommunicationsCargese, FranceMay 2023HAL back to text

Conferences without proceedings

56 inproceedingsP.Pierluigi Crescenzi, H.Hicham Lesfari, E.Emanuele Natale, A.Aurora Rossi and P.Paulo Serafim. Un framework open-source écrit en Julia pour la modélisation d'évaluation globale intégrée.ROADEF 2023 - 24ème édition du congrès annuel de la société française de recherche opérationnelle et d'aide à la décisionRennes, FranceFebruary 2023HAL DOI back to text

Doctoral dissertations and habilitation theses

57 thesisI.Igor Dias da Silva. Optimization of UAVs deployment and coordination for exploration and monitoring applications.Université Côte d'AzurSeptember 2023HAL back to text
58 thesisT.Thomas Dissaux. Graph decompositions : treelength and pursuit-evasion games.Université Côte d'AzurSeptember 2023HAL back to text

Reports & preprints

59 miscP.Pierre Aboulker, T.Thomas Bellitto, F.Frédéric Havet and C.Clément Rambaud. On the minimum number of arcs in k-dicritical oriented graphs.July 2022HAL back to text
60 reportO.Olivier Baudon, J.Julien Bensmail and M.Morgan Boivin. Interplays between variations of arbitrarily partitionable graphs under minimality constraints.Université côte d'azur; Université de Bordeaux2023HAL back to text
61 miscJ.Julien Bensmail. Arbitrarily Edge-Partitionable Graphs.January 2024HAL
62 reportJ.Julien Bensmail, T.Thomas Filasto, H.Hervé Hocquard and P.-M.Pierre-Marie Marcille. Irregularity Notions for Digraphs.Université côte d'azur; Université de bordeaux; Université paris saclay2023HAL back to text
63 reportJ.Julien Bensmail, H.Hervé Hocquard and P.-M.Pierre-Marie Marcille. Adding Direction Constraints to the 1-2-3 Conjecture.Université côte d'azur; Université de Bordeaux2023HAL back to text
64 reportJ.Julien Bensmail, H.Hervé Hocquard, P.-M.Pierre-Marie Marcille and S.Sven Meyer. On 1-2-3 Conjecture-like problems in 2-edge-coloured graphs.Université côte d'azur; Université de bordeaux; ENS Paris - Ecole Normale Supérieure de Paris2023HAL back to text
65 reportJ.Julien Bensmail. Toughness Properties of Arbitrarily Partitionable Graphs.Université côte d'azur2023HAL back to text
66 miscS.Stéphane Bessy, J.Jørgen Bang-Jensen and L.Lucas Picasarri-Arrieta. Constrained Flows in Networks.October 2023HAL back to text back to text
67 miscS.Stéphane Bessy, F.Frédéric Havet and L.Lucas Picasarri-Arrieta. Dichromatic number of chordal graphs.September 2023HAL back to text
68 reportN.Nicolas Bousquet, F.Frédéric Havet, N.Nicolas Nisse, L.Lucas Picasarri-Arrieta and A.Amadeus Reinald. Digraph redicolouring.InriaOctober 2023HAL back to text
69 miscD.David Coudert, S.Samuel Coulomb and G.Guillaume Ducoffe. Leanness Computation: Small Values and Special Graph Classes.November 2023HAL back to text
70 miscP.Pierluigi Crescenzi, E.Emanuele Natale, A.Aurora Rossi and P. B.Paulo Bruno Serafim. WorldDynamics.jl: A Julia Package for Developing and Simulating Integrated Assessment Models.June 2023HAL back to text
71 miscP.Pierluigi Crescenzi, A.Aurora Rossi and E.Emanuele Natale. An open source implementation of the Earth4All integrated assessment model.November 2023HAL
72 reportA.Arthur da Cunha, E.Emanuele Natale, D.Damien Rivet and A.Aurora Rossi. Une implémentation GPU de l'algorithme FlyHash: Des mouches plus rapides pour la fouille de données massives.INRIA; CNRS; I3S; Université Côte d'Azur2023HAL back to text
73 reportT.Thomas Dissaux, F.Foivos Fioravantes, H.Harmender Galhawat and N.Nicolas Nisse. Further results on the Hunters and Rabbit game through monotonicity.Inria - Sophia AntipolisFebruary 2023HAL back to text
74 report J.Joanna Moulierac, G.Guillaume Urvoy-Keller, M.Marco Dinuzzi and Z.Zhejiayu Ma. What is the carbon footprint of one hour of video streaming? Université Côte d'Azur April 2023 HAL back to text
75 reportN.Nicolas Nisse, L.Lucas Picasarri-Arrieta and I.Ignasi Sau. Redicolouring digraphs: directed treewidth and cycle-degeneracy.InriaJuly 2023HAL back to text
76 miscL.Lucas Picasarri-Arrieta and M.Michael Stiebitz. Minimum number of arcs in $k$ -critical digraphs with order at most $2 k - 1$ .October 2023HAL back to text

Other scientific publications

77 miscA.Aurora Rossi, S.Samuel Deslauriers-Gauthier and E.Emanuele Natale. Temporal Brain Networks Database.March 2023HAL DOI back to text
78 inproceedingsA.Aurora Rossi, E.Emanuele Natale and S.Samuel Deslauriers-Gauthier. Temporal Brain Networks Dataset.NeuroMod meeting 2023Antibes, FranceJune 2023HAL back to text
79 inproceedingsA.Aurora Rossi. Temporal Graph Neural Networks with GraphNeuralNetworks.jl.Julia and Optimization Days 2023Paris, FranceOctober 2023HAL back to text

12.3 Cited publications

80 articleJ.Jørgen Bang-Jensen and S.Stéphane Bessy. (Arc-)disjoint flows in networks.Theoretical Computer Science5262014, 28-40URL: https://www.sciencedirect.com/science/article/pii/S0304397514000280DOI back to text
81 inproceedingsR. A.Redha A. Alliche, T.Tiago da Silva Barros, R.Ramon Aparicio-Pardo and L.Lucile Sassatelli. PRISMA: A Packet Routing Simulator for Multi-Agent Reinforcement Learning.4th Intl Workshop on Network Intelligence collocated with IFIP Networking 2022Proceedings IFIP Networking Conferance 2022Catania, ItalyJune 2022HAL DOI back to text
82 softwareversionR. A.Redha A. Alliche, T.Tiago da Silva Barros, R.Ramon Aparicio-Pardo and L.Lucile Sassatelli. Packet Routing Simulator for Multi-Agent Reinforcement Learning (PRISMA) (Version v0.1).v0.1May 2022 lic: GNU General Public License version 2.HAL DOI Software Heritage VCS back to text
83 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-2HAL DOI back to text
84 inproceedingsD.Daniel Balouek, A. C.Alexandra Carpen Amarie, G.Ghislain Charrier, F.Frédéric Desprez, E.Emmanuel Jeannot, E.Emmanuel Jeanvoine, A.Adrien Lèbre, D.David Margery, N.Nicolas Niclausse, L.Lucas Nussbaum, O.Olivier Richard, C.Christian Perez, F.Flavien Quesnel, C.Cyril Rohr and L.Luc Sarzyniec. Adding Virtualization Capabilities to the Grid'5000 Testbed.Cloud Computing and Services ScienceChamSpringer International Publishing2013, 3--20back to text
85 articleJ.Jørgen Bang-Jensen, F.Frédéric Havet and A.Anders Yeo. The complexity of finding arc-disjoint branching flows.Discrete Applied Mathematics2099th International Colloquium on Graph Theory and Combinatorics, 2014, Grenoble2016, 16-26URL: https://www.sciencedirect.com/science/article/pii/S0166218X15004990DOI back to text
86 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, PolandSpringerJune 2021, 296-307HAL DOI back to text
87 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 2016HAL DOI back to text
88 inproceedingsA. O.Abdulhakeem Othman Mohammed, F. F.Feodor F. Dragan and H. M.Heather M. Guarnera. Fellow Travelers Phenomenon Present in Real-World Networks.10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 20211015Studies in Computational IntelligenceSpringer2021, 194--206URL: https://doi.org/10.1007/978-3-030-93409-5_17DOI back to text
89 articleJ. Y.J. Y. Yen. Finding the $k$ Shortest Loopless Paths in a Network.Management Science17111971, 712-716DOI back to text

COATI - 2023

COATI - 2023

2023Activity reportProject-TeamCOATI

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

Interns and Apprentices

Administrative Assistant

Visiting Scientists

External Collaborator

2 Overall objectives

3 Research program

4 Application domains

4.1 Telecommunication networks

4.2 Other Domains

5 Social and environmental responsibility

5.1 Footprint of research activities

6 Highlights of the year

6.1 New team member

6.2 Promotions

7 New software, platforms, open data

7.1 New software

7.1.1 k-shortest simple paths

7.1.2 SageMath

7.1.3 WorldDynamics.jl

7.1.4 Idawi

7.1.5 OnlineGraph

7.2 Open data

7.2.1 Temporal brain networks

7.2.2 Labeled temporal brain networks

8 New results

8.1 Network design and management

8.1.1 What is the carbon footprint of one hour of video streaming?

8.1.2 Machine learning for video streaming systems

8.1.3 Learning-based packet routing

PRISMA: A Packet Routing Simulator for Multi-Agent Reinforcement Learning

8.1.4 Modeling LoRa networks for the IoT

8.1.5 Aerial networks for sensor coverage and energy harvesting

8.1.6 Gossiping with interference in radio ring networks

8.1.7 A middleware for the experimentation on IoT mobile networks - a decentralized Web backend

8.2 Graph algorithms

8.2.1 Complexity of graph problems

Leanness of graphs

New lower bounds on the cutwidth of graphs

Constrained flows in networks

Treelength of series–parallel graphs

8.2.2 Combinatorial games in graphs

Recontamination helps a lot to hunt a rabbit

Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation

The Maker-Breaker largest connected subgraph game

Complexity of Maker-Breaker games on edge sets of graphs

8.2.3 Algorithms for social networks

A random growth model with any real or theoretical degree distribution

Preferential attachment hypergraph with vertex deactivation

8.2.4 Algorithm engineering

Algorithms for the k shortest simple paths problem

8.3 Graph and digraph theory

8.3.1 Partitioning and labelling graphs and digraphs

Distinguishing labelling problems and the 1-2-3 Conjecture

Arbitrarily partitionable graphs

Unbalanced Spanning Subgraphs in Edge Labeled Complete Graphs

Colouring decorated graphs

Colouring digraphs

Digraph redicolouring

8.3.2 Structural digraph theory

Semi-proper orientations of dense graphs

Deciding the Erdős-Pósa property in 3-connected digraphs

Inversions in digraphs

From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows

Redicolouring digraphs: directed treewidth and cycle-degeneracy

8.3.3 Metric dimension in oriented graphs

8.4 Machine learning theory and algorithms

New results on the Random Subset Sum problem and the Strong Lottery Ticket Hypothesis

A GPU implementation of the FlyHash approximate search method

Neural network information leakage through hidden learning

Algorithms for the $k$ shortest simple paths problem