Justine Cauvi

dblp:386/8366 · DBLP profile ↗
← Back
3ranked-venue papers
3as first author
3since 2021 · last 2026
0009-0001-5444-8877ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 first-author · 3 since 2021Applied, interdisciplinary, general and emerging computing · 1 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2026 Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics
abstract
In this work, we follow the current trend on temporal graph realization, where one is given a property P and the goal is to determine whether there is a temporal graph, that is, a graph where the edge set changes over time, with property P. We consider the problems where the given property P is a prescribed matrix for the duration, length, or earliest arrival time of pairwise temporal paths. This means that we are given a matrix D and ask whether there is a temporal graph such that for any ordered pair of vertices (s,t), D_{s,t} equals the duration (length, or earliest arrival time, respectively) of any temporal path from s to t minimizing that specific temporal path metric. For shortest and earliest arrival temporal paths, we are the first to consider these problems as far as we know. We analyze these problems for many settings such as: strict and non-strict paths, periodic and non-periodic temporal graphs, and limited number of labels per edge (limited number of occurrences per edge over time). In contrast to all other path metrics, we show that for the earliest arrival times, we can achieve polynomial-time algorithms in periodic and non-periodic temporal graphs and for strict and and non-strict paths. However, the problem becomes NP-hard when the matrix does not contain a single integer but a set or range of possible allowed values. As we show, the problem can still be solved efficiently in this scenario, when the number of entries with more than one value is small, that is, we develop an FPT-algorithm for the number of such entries. For the setting of fastest paths, we achieve new hardness results that answers an open question by Klobas, Mertzios, Molter, and Spirakis [Theor. Comput. Sci. '25] about the parameterized complexity of the problem with respect to the vertex cover number and significantly improves over a previous hardness result for the feedback vertex set number. When considering shortest paths, we show that the periodic versions are polynomial-time solvable whereas the non-periodic versions become NP-hard.
Justine Cauvi, Nils Morawietz, Laurent Viennot
STACS1
2025 Parameterized Restless Temporal Path
Justine Cauvi, Laurent Viennot
FCT1
2024 Landmark Hub Labeling: Improved Bounds and Faster Query Answering
Justine Cauvi, Ruoying Li 0001, Sabine Storandt
ATMOS1