Proposition de thèse au Le Havre sur les graphes dynamiques (PhD proposal)

Description du projet de these: Questions de connexité dans les graphes dynamiques.

(english version below)

 

Lieu et financement

La thèse est au sein de l'équipe RI2C (Réseaux d'Interaction et Intelligence Collective) du laboratoire LITIS, et se déroule à l'université du Havre. Elle est financée par le projet ANR TEMPOGRAL commencé en novembre 2022.

 

Contexte

De nombreux problèmes combinatoires sur les graphes ont été étudiés dans la littérature, et l'on connait dans bien des cas les algorithmes les plus efficaces pour les résoudre. Mais il n'en est pas de même dans le cas dynamique. En effet, adapter un problème usuel de graphes aux graphes dynamiques (aussi appelés graphes temporels) n'est pas simple. Si la question est mal posée, le dynamisme du graphe risque de ne pas du tout influer sur la méthode de résolution. Prenons l'exemple des ensembles stables, c'est-à-dire d'ensembles de sommets non adjacents deux à deux. Si l'on généralise un stable aux graphes dynamiques en suggérant que cela doit être un ensemble stable de chacun des états du graphe, alors le problème revient simplement à trouver un stable du graphe obtenu en sélectionnant simultanément toutes les arêtes qui apparaissent au moins une fois dans le graphe dynamique (le graphe union, aussi appelé le graphe sous-jacent). La notion de dynamisme perd alors tout son sens : on s'est ramené à un problème purement statique classique. Inversement, il existe de nombreux problèmes de flots dynamiques, dans lesquels la solution elle-même est évolutive (flot défini aux différents pas de temps), voir par exemple [2]. Étant donné un problème et un modèle de graphes dynamiques sur lequel le résoudre il s'agit alors de concevoir un algorithme, le plus efficace possible, pour calculer une solution du problème. Il s'agit d'abord de comprendre le problème et d'analyser les paramètres du modèle influençant la complexité d'algorithmes de résolution.

Les problèmes peuvent être de 3 types au moins : génération [3, 9], optimisation sur graphes dynamiques [2,4,13], recherche de stratégies optimales dans les jeux sur les graphes [5,6].  De plus chaque problème peut s'appliquer à différents modèles de graphes dynamiques et dans plusieurs cadres algorithmiques, par exemple : algorithmes hors ligne déterministes (le graphe dynamique ciblé est entièrement connu) ; algorithmes hors ligne stochastiques (l'évolution du graphe est connue par un modèle probabiliste) ; algorithmes en ligne (algorithme exécuté à chaque changement du graphe). Ce large nombre de possibilités problème-modèle ouvre donc de très nombreuses questions algorithmiques.

Il n'est pas question de traiter toutes ces questions lors d'une seule thèse. En fait, certaines ont déjà été abordées dans les travaux de l'équipe RI2C, depuis les travaux pionniers sur le logiciel GraphStream [7]. Il s'agit donc d'une recherche incrémentale, en lien avec de nombreux projets de l'équipe de recherche RI2C. RI2C s'est positionné avec un succès grandissant sur ces questions d'algorithmique dans les graphes dynamiques, et il s'agit maintenant d'une thématique phare, dans le contexte plus large des systèmes complexes.

Les flots dynamiques, l'étude de composantes connexes particulières, étaient le sujet de la thèse de Mathilde Vernet [8]. Jason Schoeters a mené à bien durant son post doc une classification exhaustive des différentes composantes, et de la difficulté de les calculer [16]. Le post-doctorat de Ioannis Lamprou considérait le jeu dit des gendarmes et voleurs dans un cadre dynamique [6]. Les questions de génération, de morphogénèse, ont été traités dans la thèse de Michele Tirico [9]. La thèse de Vincent Bridonneau débutée en 2020 se focalise sur des questions de stabilisation des graphes générés [17].

D'autres travaux sur les graphes ou les réseaux dynamiques ont été menés dans l'équipe sur des applications diverses, faisant souvent appel à des coopérations multidisciplinaires. Nous travaillons avec des géographes (projet régional PORTERR), des mathématiciens (projet ANR COM2SICA), des spécialistes des sports [14]. D'un point de vue plus large, il y a une vraie dynamique au niveau régional sur ces questions, avec en particulier une collaboration avec le laboratoire Caennais GREYC concrétisée par le projet RIN DynNet [11] et des stages communs dans le cadre de la fédération NormaStic.

Nous sommes partenaires de deux projets ANR. Le premier, MAGNETICS, analyse les réseaux maritimes comme des graphes dynamiques dans une perspective résolument pluridisciplinaire (Économistes, géographes, informaticiens). La dynamique est ici présente sur le temps long (données historiques).

Le second, TEMPOGRAL [15], se propose de fournir de nouveaux outils pour l'analyse des graphes dynamiques. Les trois équipes partenaires de ce projet regroupent une part conséquente des chercheurs Français du domaine. TEMPOGRAL finance cette thèse. La ou le doctorant.e travaillera en lien fort avec les autres partenaires du projet (laboratoires IRIF à Paris et LABRI à Bordeaux), et y effectuera des séjours de recherche.

 

Projet détaillé

La thèse se place dans le prolongement de la thèse de Mathilde Vernet [8] (soutenance octobre 2021) et du post-doctorat de Jason Schoeters [16] (oct 2021 - décembre 2022).

Nous nous focaliserons dans cette thèse sur les problèmes algorithmiques nés de la notion de connectivité au sens large. Cette notion est la clé permettant d'attaquer des problèmes comme l'acheminement d'informations, d'énergie, de marchandises, de voyageurs d'un noeud du réseau à un autre ; C'est-à-dire de nombreux problèmes issus de la logistique et du transport. Dans ces applications, la dynamicité du réseau sous-jacent peut avoir plusieurs causes. Sur une échelle de temps assez courte, les liens de communication peuvent devenir indisponibles pour des raisons diverses : par exemple travaux sur une route ou une ligne ferroviaire, mais aussi contention du lien (bouchon sur un axe routier). Sur une échelle plus longue, c'est la structure du réseau qui change avec l'ajout de nouvelles liaisons (par exemple maritimes ou ferroviaires) mais aussi leur retrait. De nouveaux noeuds peuvent aussi apparaître suite par exemple à la mise en service de nouvelles infrastructures logistiques (transport ou stockage), de production, ou de consommation.

Quelles que soient les sources de la dynamique de ces réseaux, les problèmes autour du maintien de la connexité, de la recherche de chemins conservant certaines caractéristiques, sont primordiaux pour leur utilisation optimale. Nous étudierons dans cette thèse les différentes façons de considérer la connexité en dynamique. Nous nous appuierons d'une part sur le travail pionnier d'Arnaud Casteigts [12] sur la classification des différentes connexités, et d'autre part sur les travaux en interne sur la notion de composante connexe (travaux de Mathilde Vernet [4], et de Jason Schoeters [16]). Plus précisément, nous nous intéresserons aux versions dynamiques des problèmes classiques comme les plus courts chemins, arbres couvrants, composantes connexes maximales, arbres de Steiner, tournées, ... Nous chercherons à caractériser les classes de graphes dynamiques pour lesquels ces problèmes : 1/ ont du sens 2/ sont faciles à résoudre, ou non. Cette deuxième question est sans doute fortement corrélée avec le fait qu'un problème puisse être résolu en adaptant des algorithmes classiques, ou nécessite la conception d'algorithmes spécifiques. Une fois établie le degré de difficulté de ses problèmes, l'objectif de la thèse est de concevoir et analyser des algorithmes efficaces pour les résoudre.

Il reste des questions intéressantes concernant l'extension des composantes connexes au cas dynamique. La notion de connexité est souvent préalable à l'étude de problèmes plus complexes, et la.le doctorant.e pourra se « faire les dents » sur cette question, pour bien comprendre les caractéristiques spécifiques du travail sur les graphes dynamiques.

Le premier problème concret qui sera traité dans cette thèse est celui du problème de voyageur de commerce (Traveling Salesman Problem, TSP). Également décrit comme le problème de tournée de véhicules, le TSP est un problème classique dans le domaine de la logistique portuaire et du transport de marchandise. Son adaptation au contexte dynamique qui reflète les environnements multimodaux du tissu économique local et régional est tout à fait pertinent. Dans le contexte temporel, on associe à chaque arête des dates de présence (étiquettes) [18]. Le TSP temporel consiste à construire une suite d'arêtes permettant de passer par tous les sommets du graphe. La suite d'arêtes forme un cycle, mais de plus une solution réalisable associe à chaque arête une de ses dates de présence, de sorte que la suite des étiquettes obtenues est strictement croissante. Dans une version « faible » du problème, il est autorisé de passer plusieurs fois par un même sommet (on parle alors d'exploration temporelle [19]). On sait que décider si un graphe statique admet un cycle Hamiltonien est déjà un problème NP-Complet. La variante temporelle est également difficile même sous des hypothèses très restrictives.

Nous nous intéresserons à la question suivante : quel est la durée minimale d'une exploration temporelle (définie comme la valeur de sa plus grande étiquette) ? Plus précisément, on peut montrer avec quelques hypothèses naturelles sur les étiquettes que cette durée est au maximum de l'ordre de n². Mais peut-on toujours trouver une solution dont la durée est au plus de l'ordre de m, nombre d'arêtes du graphe ? Ce problème algorithmique contraint par les barrières de sa complexité algorithmique constitue le premier verrou scientifique de cette thèse.

Le second problème que nous souhaitons traiter est celui de l'adaptation du problème de l'arbre de Steiner au cas dynamique. Dans le modèle statique ce problème vise à relier par un arbre (le plus souvent minimal) les sommets d'un ensemble donné de sommets terminaux. Au-delà de deux terminaux ce problème est NP-Complet. Il l'est également dans un contexte dynamique. Mais la définition du modèle dynamique détermine le type de solutions possible ainsi que leur complexité [19]. Il convient d'étudier la définition du problème avant d'en déterminer la complexité. Par exemple, la figure suivante illustre un graphe a deux terminaux, k pas de temps et deux ensembles de sommets « a » et « b » répondant à deux problématiques différentes. L'ensemble « b » contient le plus court chemin présent à chaque étape de temps (1,2,..., k). L'ensemble « a » contient un plus court chemin à chaque pas de temps.

Ici encore le verrou scientifique se situe dans la difficulté algorithmique du passage au cas dynamique, ainsi que dans la redéfinition du problème.

 

Bibliographie

(les noms des encadrants sont en gras)

[1] Holme, P. (2015). Modern temporal network theory: a colloquium. The European Physical

Journal B 88 (9), 234.

[2] M. Vernet, M. Drozdowski, Y. Pigné, E. Sanlaville (2020). A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs. Discrete Applied Mathematics, ?10.1016/j.dam.2019.12.012?.

[3] Tirico, M., Balev, S., Dutot, A., & Olivier, D. (2018). Morphogenesis of Complex Networks: A Reaction Diffusion Framework for Spatial Graphs. In International Conference on Complex Networks and their Applications (pp. 769-781). Springer, Cham.

[4] M. Vernet, Y. Pigné, E. Sanlaville (2022) A study of connectivity on dynamic graphs: computing persistent connected components. 4OR-Q J Oper Res. https://doi.org/10.1007/s10288-022-00507-3.

[5] P. Dorbec, M. A. Henning, C. Löwenstein, M. Montassier, A. Raspaud (2013). Generalized power domination in regular graphs. SIAM J. Discrete Math., 2 7(3):1559?1574

[6] S. Balev, I. Lamprou, J.L. Jimenez Laredo, Y. Pigné, E. Sanlaville (2020) Cops and Robber on Dynamic Graphs:Offline and Online Case. International Colloquium on Structural Information and Communication Complexity SIROCCO 2020 (pp. 203-219). Springer, Cham. Accepted in DMTCS, 2023.

[7] Dutot, A., F. Guinand, D. Olivier, and Y. Pigné (2007). Graphstream: A tool for bridging the gap between complex systems and dynamic graphs. In Emergent Properties in Natural and Artificial Complex Systems. Satellite Conference within the 4th European Conference on Complex Systems (ECCS?2007).

[8] Vernet, M : Modèles et algorithmes pour les graphes dynamiques, thèse de l'université Le Havre Normandie, octobre 2020. Directeur E. Sanlaville, co-encadrant Y. Pigné.

[9] Tirico, M : Morphogénèse de réseaux complexes, thèse de l'université Le Havre Normandie, novembre 2020. Directeur D. Olivier, co-encadrants S. Balev, A. Dutot.

[10] F. Guinand, Y. Pigné. Time considerations for the study of complex maritime networks. In Maritime Networks: Spatial structures and time dynamics, Routledge, pp.163-189, 2015.

[11] DynNet : Dynamic Networks. Projet RIN Tremplin 2020. GREYC équipe HAMAC (porteur), LITIS équipe RI2C.

[12] Casteigts, A., Chaumette, S., & Ferreira, A. (2009, May). Characterizing topological assumptions of distributed algorithms in dynamic networks. In International Colloquium on Structural Information and Communication Complexity (pp. 126-140). Springer, Berlin, Heidelberg.

[13] Vernet, M., Balev, S., Pigné, Y., Sanlaville, E. (2020). On the complexity of the Dynamic Steiner Tree problem, working paper.

[14] Bourgeais, Q. Réseaux dynamiques dans les sports collectifs : analyse et applications, thèse de l'université de Rouen Normandie, co-encadrée par L. Seifert (CETAPS), E. Sanlaville, R. Charrier (LITIS), Débutée en novembre 2021.

[15] Projet ANR TEMPOGRAL (Problèmes algorithmiques sur les graphes temporels) https://www.labri.fr/perso/acasteig/tempogral/

[16] S. Balev, Y. Pigné, É. Sanlaville, J. Schoeters. Temporally connected components. 2023. En cours de soumission.

[17] V. Bridonneau, F. Guinand, Y. Pigné. Dynamic Graphs Generators Analysis : an Illustrative Case Study. LITIS, Le Havre Normandie University. 2022. En cours de soumission.

[18] O. Michail and P. G. Spirakis. Traveling salesman problems in temporal graphs. In 39th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 553?564. Springer, 2014.

[19] Imase M, Waxman BM (1991) Dynamic Steiner Tree Problem. SIAM J Discrete Math 4:369?384. https://doi.org/10.1137/0404033

 

Prérequis

La ou le candidat.e devra être titulaire d'un master ou diplôme d'ingénieur en informatique ou mathématiques appliquées. Elle ou il devra avoir des connaissances approfondies en théorie des graphes et en algorithmique.

 

Contacts

Stefan Balev, Yoann Pigné, Eric Sanlaville (prenom.nom@univ-lehavre.fr)

 

 

 

 

Description of the thesis project: Issues on connectivity in dynamic graphs.

 

Location and funding

The thesis is proposed by the RI2C team (Interaction Networks and Collective Intelligence) of the LITIS laboratory, and takes place at the University of Le Havre. It is financed by the ANR TEMPOGRAL project, which started in November 2022.

 

Background

Many combinatorial problems on graphs have been studied in the literature, and in many cases the most efficient algorithms to solve them are known. But it is not the same in the dynamic case. Indeed, adapting a usual graph problem to dynamic graphs (also called temporal graphs) is not simple. If the question is poorly formulated, the dynamism of the graph may not influence the solution method at all. Let us take the example of independent sets, i.e. sets of vertices that are not adjacent to each other. If we generalize an independent set to dynamic graphs by suggesting that it must be an independent set of each of the states of the graph, then the problem simply amounts to finding an independent set of the graph obtained by simultaneously selecting all the edges that appear at least once in the dynamic graph (the union graph, also called the underlying graph). The notion of dynamism then loses all its meaning: we are back to a purely static classical problem. Conversely, there are many dynamic flow problems, in which the solution itself is evolutive (flow defined at different time steps), see for example [2]. Given a problem and a model of dynamic graphs on which to solve it, it is then a matter of designing an algorithm, as efficient as possible, to compute a solution of the problem. The first step is to understand the problem and to analyze the parameters of the model that influence the complexity of the solution algorithms.

The problems can be of at least 3 types: generation [3, 9], optimization on dynamic graphs [2,4,13], finding optimal strategies in games on graphs [5,6]. Moreover, each problem can be applied to different models of dynamic graphs and in several algorithmic frameworks, e.g.: deterministic offline algorithms (the targeted dynamic graph is fully known); stochastic offline algorithms (the evolution of the graph is known by a probabilistic model); online algorithms (algorithm executed at each change of the graph). This large number of problem-model possibilities opens up many algorithmic questions.

It is not possible to address all these issues in a single thesis. In fact, some of them have already been addressed in the works of the RI2C team, since the pioneering work on the GraphStream software [7]. It is therefore an incremental research, linked to many projects of the RI2C research team. RI2C has positioned itself with increasing success on these algorithmic issues in dynamic graphs, and it is now a flagship theme, into the broader context of complex systems.

Dynamic flows, the study of particular related components, were the subject of Mathilde Vernet's thesis [8]. Jason Schoeters carried out during his postdoc an exhaustive classification of the different components, and the difficulty to compute them [16]. The post-doc of Ioannis Lamprou considered the game of cops and robbers in a dynamic framework [6]. The questions of generation, of morphogenesis, were treated in the thesis of Michele Tirico [9]. Vincent Bridonneau's thesis started in 2020 and focuses on stabilization issues of generated graphs [17].

Other works on graphs or dynamic networks have been carried out in the team on various applications, often involving multidisciplinary cooperation. We work with geographers (regional project PORTERR), mathematicians (ANR project COM2SICA), sports specialists [14]. From a broader point of view, there is a real dynamic at the regional level on these questions, with in particular a collaboration with the Caen laboratory GREYC concretized by the RIN project DynNet [11] and common training courses within the NormaStic federation.

We are partners in two ANR projects. The first one, MAGNETICS, analyses maritime networks as dynamic graphs in a resolutely multidisciplinary perspective (economists, geographers, computer scientists). The dynamics are present here on the long term (historical data).

The second one, TEMPOGRAL [15], aims at providing new tools for the analysis of dynamic graphs. The three partner teams of this project gather a significant part of the French researchers in this field. TEMPOGRAL is funding this thesis. The PhD student will work in close collaboration with the other partners of the project (IRIF laboratory in Paris and LABRI laboratory in Bordeaux), and will carry out research stays there.

 

Detailed project

The thesis is a continuation of Mathilde Vernet's thesis [8] (defense October 2021) and Jason Schoeters' post-doctorate [16] (Oct 2021 - Dec 2022).

In this thesis, we will focus on the algorithmic problems arising from the notion of connectivity in the broadest sense. This notion is the key to tackle problems such as the routing of information, energy, goods, travelers from one network node to another; that is to say, many problems arising from logistics and transportation. In these applications, the dynamics of the underlying network can have several causes. On a short time scale, communication links may become unavailable for various reasons: for example, road or rail works, but also link contention (traffic jam on a road). On a longer scale, it is the structure of the network that changes with the addition of new links (e.g., maritime or rail) but also their removal. New nodes may also appear, for example, following the commissioning of new logistics (transport or storage), production or consumption infrastructures.

Whatever the sources of the dynamics of these networks, the problems around the maintenance of connectedness, the search for paths preserving certain characteristics, are paramount for their optimal use. In this thesis, we will study the different ways of considering connectedness in dynamics. We will rely on the pioneering work of Arnaud Casteigts [12] on the classification of different connectivities, and on our work on the notion of connected component (work of Mathilde Vernet [4], and Jason Schoeters [16]). More precisely, we will be interested in dynamic versions of classical problems such as shortest paths, spanning trees, maximum related components, Steiner trees, tours, ... We will try to characterize the classes of dynamic graphs for which these problems: 1/ make sense 2/ are easy to solve, or not. This second question is probably strongly correlated with the possibility that a problem can be solved by adapting classical algorithms, or conversely requires the design of specific algorithms. Once the degree of difficulty of these problems is established, the objective of the thesis is to design and analyze efficient algorithms to solve them.

There are still interesting questions concerning the extension of related components to the dynamic case. The notion of connectivity is often a prerequisite to the study of more complex problems, and the PhD student will be able to "cut his teeth" on this question, to understand the specific characteristics of working on dynamic graphs.

The first concrete problem that will be addressed in this thesis is the Traveling Salesman Problem (TSP). Close to the vehicle routing problem, the TSP is a classical problem in the field of port logistics and freight transportation. Its adaptation to the dynamic context that reflects the multimodal environments of the local and regional economic world is quite relevant. In the temporal context, we associate presence dates (labels) to each edge [18]. The temporal TSP consists of constructing a sequence of edges that allows passing through all vertices of the graph. The sequence of edges forms a cycle, but moreover a feasible solution associates to each edge one of its presence dates, so that the sequence of labels obtained is strictly increasing. In a "weak" version of the problem, it is allowed to pass several times through the same vertex (this is called temporal exploration [19]). It is known that deciding whether a static graph admits a Hamiltonian cycle is already an NP-complete problem. The temporal variant is also difficult even under very restrictive assumptions.

We are interested in the following question: what is the minimal duration of a temporal exploration (defined as the value of its largest label)? More precisely, we can show with some natural assumptions on the labels that this duration is at most of the order of n². But can we always find a solution whose duration is at most of the order of m, number of edges of the graph? This algorithmic problem constrained by the barriers of its algorithmic complexity constitutes the first scientific lock of this thesis.

The second problem we wish to address is the adaptation of the Steiner tree problem to the dynamic case. In the static model, this problem aims at linking by a tree (most often minimal) the vertices of a given set of terminal vertices. With more than two terminals this problem is NP-complete. It is also NP-complete in a dynamic context. But the definition of the dynamic model determines the type of possible solutions as well as their complexity [19]. It is appropriate to study the definition of the problem before determining its complexity. For example, the following figure illustrates a graph with two terminals, k time steps, and two sets of vertices "a" and "b" addressing two different problems. The set " b " contains the shortest path among those present at each time step (1,2,..., k). The set "a" contains a shortest path at each time step .

Here again, the research problem lies in the algorithmic difficulty of the transition to the dynamic case, as well as in the redefinition of the problem.

 

Bibliography 

(supervisors' names are in bold)

[1] Holme, P. (2015). Modern temporal network theory: a colloquium. The European Physical

Journal B 88 (9), 234.

[2] M. Vernet, M. Drozdowski, Y. Pigné, E. Sanlaville (2020). A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs. Discrete Applied Mathematics, ?10.1016/j.dam.2019.12.012?.

[3] Tirico, M., Balev, S., Dutot, A., & Olivier, D. (2018). Morphogenesis of Complex Networks: A Reaction Diffusion Framework for Spatial Graphs. In International Conference on Complex Networks and their Applications (pp. 769-781). Springer, Cham.

[4] M. Vernet, Y. Pigné, E. Sanlaville (2022) A study of connectivity on dynamic graphs: computing persistent connected components. 4OR-Q J Oper Res. https://doi.org/10.1007/s10288-022-00507-3.

[5] P. Dorbec, M. A. Henning, C. Löwenstein, M. Montassier, A. Raspaud (2013). Generalized power domination in regular graphs. SIAM J. Discrete Math, 2 7(3):1559-1574

[6] S. Balev, I. Lamprou, J.L. Jimenez Laredo, Y. Pigné, E. Sanlaville (2020) Cops and Robber on Dynamic Graphs:Offline and Online Case. International Colloquium on Structural Information and Communication Complexity SIROCCO 2020 (pp. 203-219). Springer, Cham. Accepted in DMTCS, 2023.

[7] Dutot, A., F. Guinand, D. Olivier, and Y. Pigné (2007). Graphstream: A tool for bridging the gap between complex systems and dynamic graphs. In Emergent Properties in Natural and Artificial Complex Systems. Satellite Conference within the 4th European Conference on Complex Systems (ECCS'2007).

[8] Vernet, M: Models and algorithms for dynamic graphs, thesis of the University of Le Havre Normandie, October 2020. Director E. Sanlaville, co-supervisor Y. Pigné.

[9] Tirico, M: Morphogenesis of complex networks, thesis of the University of Le Havre Normandie, November 2020. Director D. Olivier, co-supervisors S. Balev, A. Dutot.

[10] F. Guinand, Y. Pigné. Time considerations for the study of complex maritime networks. In Maritime Networks: Spatial structures and time dynamics, Routledge, pp.163-189, 2015.

[11] DynNet: Dynamic Networks. RIN Tremplin 2020 project. GREYC team HAMAC (leader), LITIS team RI2C.

[12] Casteigts, A., Chaumette, S., & Ferreira, A. (2009, May). Characterizing topological assumptions of distributed algorithms in dynamic networks. In International Colloquium on Structural Information and Communication Complexity (pp. 126-140). Springer, Berlin, Heidelberg.

[13] Vernet, M., Balev, S., Pigné, Y., Sanlaville, E. (2020). On the complexity of the Dynamic Steiner Tree problem, working paper.

[14] Bourgeais, Q. Réseaux dynamiques dans les sports collectifs : analyse et applications, thesis from the University of Rouen Normandie, co-supervised by L. Seifert (CETAPS), E. Sanlaville, R. Charrier (LITIS), Started in November 2021

[15] ANR project TEMPOGRAL (Algorithmic problems on temporal graphs) https://www.labri.fr/perso/acasteig/tempogral/

[16] S. Balev, Y. Pigné, É. Sanlaville, J. Schoeters. Temporally connected components. 2023. In submission.

[17] V. Bridonneau, F. Guinand, Y. Pigné. Dynamic Graphs Generators Analysis: an Illustrative Case Study. LITIS, Le Havre Normandie University. 2022. In progress.

[18] O. Michail and P. G. Spirakis. Traveling salesman problems in temporal graphs. In 39th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 553-564. Springer, 2014.

[19] Imase M, Waxman BM (1991) Dynamic Steiner Tree Problem. SIAM J Discrete Math 4:369-384. https://doi.org/10.1137/0404033

 

Prerequisites

The candidate should have a master's degree or an engineering degree in computer science or applied mathematics. He or she should have a thorough knowledge of graph theory and algorithms.

 

Contacts

Stefan Balev, Yoann Pigné, Eric Sanlaville (firstname.name@univ-lehavre.fr)