Postdoc in temporal graphs

Back to jobs listing

INRAE presentation

The French National Research Institute for Agriculture, Food, and Environment (INRAE) is a major player in research and innovation. It is a community of 12,000 people with 272 research, experimental research, and support units located in 18 regional centres throughout France. Internationally, INRAE is among the top research organisations in the agricultural and food sciences, plant and animal sciences, as well as in ecology and environmental science. It is the world’s leading research organisation specialising in agriculture, food and the environment. INRAE’s goal is to be a key player in the transitions necessary to address major global challenges. Faced with a growing world population, climate change, resource scarcity, and declining biodiversity, the Institute has a major role to play in building solutions and supporting the necessary acceleration of agricultural, food and environmental transitions.

Work environment, missions and activities

The research unit Technologies et Systèmes d'Information pour les Agrosystèmes (TSCF) and the LIMOS laboratory (Université Clermont Auvergne) are hiring a postdoctoral fellow in algorithmic graph theory. This position is open in the project DcoDE (Data Collection in Dynamic Environments).

 

Recent work at TSCF has focused on agricultural sensors, which have to be placed in specific ways to avoid disturbing work. An option is then to bury the sensors, requiring an active collection of data. The use of a drone has been studied, with an approach consisting in constructing a graph from the disks of data emission of all sensors, and solving a TSP to compute a tour [1]. The goal of the project DcoDE is to investigate further this idea, by exploring the following research goals:

- proposing different ways to generate the graph on which the tour is computed. The current approach is a heuristics reducing two intersecting disks to their intersection, and iterating until all disks are disjoint, which does not necessarily produce ‘good’ graphs, and ignores the possibility to collect data at some points in the field;

- adding weather prediction to the model, since the wind can increase the cost of movement at some time-steps, this implies studying the temporal version of TSP [3], or other problems modeling the exploration of special vertices in a temporal graph [2];

- enumerating acceptable and significantly different solutions, using enumeration-efficient methods, in order to have several options of tours for an end user.

The main contributions will be theoretical, but implementations and experimental results on datasets from the research unit will be viewed favorably.

The recruited fellow will be supervised by Antoine Dailly (TSCF) and Vincent Limouzy (LIMOS). They will be expected to take part in the AlCoLoCo research group (https://alcoloco.isima.fr/).

[1] C. Cariou, L. Moiroux-Arvis, F. Bendali and J. Mailfert (2024). Optimal Route Planning of an Unmanned Aerial Vehicle for Data Collection of Agricultural Sensors. IEEE INFOCOM 2024 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Vancouver, BC, Canada, 2024, pp. 1-6.

[2] A. D'Ascenzo, G. F. Italiano, S. Kanellopoulos, A. Mpanti, A. Pagourtzis and C. Pergaminelis (2025). Beer Path Problems in Temporal Graphs. arXiv preprint arXiv:2507.08685, to be presented at IWOCA 2026.

[3] O. Michail and P. G. Spirakis (2016). Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634, 1-23.

Training and skills

Recommended training: PhD in computer science or mathematics, with a focus on algorithmic graph theory.

Desired knowledge: Algorithms, Graph theory.

Appreciated experience: Temporal graphs, enumeration, programing.

INRAE's life quality

By joining our teams, you benefit from (depending on the type of contract and its duration):

- up to 30 days of annual leave + 15 days "Reduction of Working Time" (for a full time);
- parenting support: CESU childcare, leisure services;
- skills development systems: training, career advise;
- social support: advice and listening, social assistance and loans;
- holiday and leisure services: holiday vouchers, accommodation at preferential rates;
- sports and cultural activities;
- collective catering.

The Cézeaux site is served by subway line A, and is also equipped with parking facilities and services dedicated to cycling.

How to apply

I send my CV and my motivation letter