4 papers · 1 filter
Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics
Justine Cauvi, Nils Morawietz, Laurent Viennot
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…
Temporal Graph Realization With Bounded Stretch
George B. Mertzios, Hendrik Molter, Nils Morawietz +1
A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first time steps, and then it reappears recurrently every time s…
Realization of Temporally Connected Graphs Based on Degree Sequences
Arnaud Casteigts, Michelle Döring, Nils Morawietz
Given an undirected graph , the problem of deciding whether admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al.,…
Recognizing and Realizing Temporal Reachability Graphs
Thomas Erlebach, Othon Michail, Nils Morawietz
A temporal graph can be represented by an underlying graph together with a function that assigns to each edge the set of time steps durin…