Hello the LITIS Laboratory in Le Havre, Normandy, France, proposes a funded PhD thesis on exploring temporal graphs, with a co-supervision with Patras university (Greece). More details below. Please broadcast this information to any interested student. Best regards Eric *Project title: Exploration of temporal graphs. Application to logistics networks.* Host institution: ULHN University of Le Havre Normandy, France Laboratory : LITIS UR 4108 Starting date: september or october 2026 A temporal graph [1] is a graph with n vertices whose set of edges evolves over time. This evolution may be entirely known, or not. In the latter case, we refer to it as a dynamic graph. If this evolution can be represented using a probabilistic model, it is similar to random graphs (an edge is present with a certain probability). If we do not have such a model, we refer to it as an online problem. A temporal or dynamic graph can be represented as a sequence of static graphs with the same vertices; these graphs are called snapshots. Finally, the static graph containing all the edges present during the lifetime of the graph is called the underlying graph. When modeling transportation networks, an edge is often associated with a travel time or transportation time. For example, an edge representing a shipping line will be associated with a duration measured in days at sea. The same applies to road transport, information transport, etc. It should be noted here that the most fundamental works on temporal graphs generally assume a unit travel time. Sometimes, on the contrary, travel time is neglected in relation to the dynamics of network evolution (transport, generally of information or energy, is much faster than the speed of network evolution). These different assumptions have consequences for the generalization of path in a temporal setting.Such a pathis referred to as a journey(or temporal path). It is a sequence of edges associated with increasing start dates for the crossing, which must comply with the presence of the edges and their travel times. If there are journeysbetween any pair of vertices during the lifetime of the graph, we say that it is temporally connected. If each snapshot is connected, we say that the graph is constantlyoralways-connected. Using these two concepts, one can defineconnected components, either temporal or instantaneous. We have studied these two types of components (and their many variants). Interestingly, determining temporally connected components is very often NP-hard even for unit traversal times [2], while determining instantaneously connected components is polynomial [3]. A related problem is that of exploring a temporal or dynamic graph. An exploration is a temporal path which visits each vertex of the graph at least once. For a fixed lifetime, the graph may be temporally connected without being explorable. The literature on this subject is fairly recent but is growing rapidly. The graphs generally studied in the literature are constantly connected, with unit traversal times. There are two fairly natural questions. The first is the existence of such a path for a given lifetime, and conversely, the minimum lifetime (number of time steps) required to find such a path. The second is what is the minimum number of edges that must be traversed by such a path. There are many results on the first question, see for example [4], but much less on the second, which is the subject of Antoine Toullalan's thesis, scheduled to be defended in 2026 [5]. We know that for any underlying graph, O(n²) time steps are sufficient (and sometimes necessary) to explore a temporal graph. The main result of Antoine Toullalan's thesis is that O(n^1.5 ) edge traversals are sufficient. However, we do not have any example with more than a linear number of edge traversals, whereas for several classes of graphs this number is linear in n. Our conjecture is that 2n-3 edge traversals are always sufficient, given O(n²) time steps. Our objectives are to continue the work of A. Toullalan's thesis in three directions, in order to obtain results on models that are closer to the reality of actual logistics networks. 1) Still in the case of a single time unit for traversing edges and known evolution, study this conjecture by considering new classes of graphs. 2) Consider dynamic graphs, based on random graph models [6,7,8]. There are still few studies, and all focus on the existence of explorations depending on the lifetime of the graph, as in [4]. We wish to study the problem of the minimum number of edges to cross in this context. 3) Variable traversal times. There is still nothing in the literature on exploration in this context. It is certainly possible to use the well-known model of expended graphs, but this will lead to highly complex algorithms. Are other approaches possible? 4) It is of course possible to combine random graphs and arbitrary traversal times, and we would like to obtain results in this general framework. *Bibliograph**y * [1] Holme, P. (2015). Modern temporal network theory: a colloquium./The European Physical Journal B/88 (9), 234. [2] *Balev, S.*, *Sanlaville, E.*, & Schoeters, J. (2024). Temporally connected components. /Theoretical Computer Science/, /1013/, 114757. *[3] **_M. _**_Vernet,_****_Y. Pigné_**, ***E. Sanlaville***(2022) A study of connectivity on dynamic graphs: computing persistent connected components. 4OR-Q J Oper Res. * [4] Erlebach, T., Hoffmann, M., and Kammer, F. "On temporal graph exploration." /Journal of Computer and System Sciences/119 (2021): 1-18. [5] *Balev, S.*, *Sanlaville, É.*, & _Toullalan, A._(2025). Brief Announcement: The Shortest Temporal Exploration Problem. In /4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)/(pp. 18-1). Schloss Dagstuhl–Leibniz-Zentrum für Informatik. [6] Casteigts, A., Raskin, M., Renken, M., & Zamaraev, V. (2024). Sharp thresholds in random simple temporal graphs. /SIAM Journal on Computing/, /53/(2), 346-388. [7] *Nikoletseas, S.*, *Raptopoulos, C.*, & Spirakis, P. (2023). Max cut in weighted random intersection graphs and discrepancy of sparse random set systems. /Algorithmica/, /85/(9), 2817-2842. [8] Mertzios, G. B., *Nikoletseas, S.*, *Raptopoulos, C.*, & Spirakis, P. G. (2024). Brief Announcement: On the existence of δ-temporal cliques in random simple temporal graphs. SAND2024. /Leibniz International Proceedings in Informatics, LIPIcs/, /292/. [9] Akrida, E C, Mertzios, G B, Spirakis, P G,and *Raptopoulos, C. *"The temporal explorer who returns to the base." /Journal of Computer and System Sciences/120 (2021): 179-193. [10] Baguley, S., Göbel, A., Klodt, N., Skretas, G., Sylvester, J., Zamaraev,V.,Temporal Exploration of Random Spanning Tree Models.Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).[11] Projet ANR TEMPOGRAL (Problèmes algorithmiques sur les graphes temporels), *Eric Sanlaville*porteur. labri.fr/perso/acasteig/tempogral/ Thesis supervision The PhD student will be registered at Le Havre University. However, the recruited person will be co-supervised by Eric Sanlaville and Stefan Balev from Le Havre, and Sotiris Nikoletseas and Christoforos Raptopoulos from Patras University (Greece). He/she will do several sojourns to Patras. Candidate profile : The candidates must have a master degree or equivalent in computer science or applied mathematics, with a strong background in algorithmics and graph theory. English langage proficiency is needed, French and Greek would be appreciated but are not mandatory. To candidate, please provide a CV, short motivation letter and master marks to the supervisors: eric.sanlaville@univ-lehavre.fr, stefan.balev@univ-lehavre.fr, nikole@cti.gr, raptopox@upatras.gr (The complete application is due by April 29) -- Eric Sanlaville co-directeur LITIS Professeur d'Informatique Université Le Havre Normandie ********************************************************** * * Contributions to be spread via DMANET are submitted to * * DMANET@zpr.uni-koeln.de * * Replies to a message carried on DMANET should NOT be * addressed to DMANET but to the original sender. The * original sender, however, is invited to prepare an * update of the replies received and to communicate it * via DMANET. * * DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET) * http://www.zaik.uni-koeln.de/AFS/publications/dmanet/ * **********************************************************