3 papers
cs.DM2026
Sharp Thresholds for Temporal Motifs and Doubling Time in Random Temporal Graphs
Henry Austin, George B. Mertzios, Paul G. Spirakis
In this paper we study two natural models of random temporal graphs. In the first, the continuous model, each edge is assigned labels, each drawn uniformly at random from…
cs.DS2025
Maintaining Bipartite Colourings on Temporal Graphs on a Budget
Duncan Adamson, George B. Mertzios, Paul G. Spirakis
Graph colouring is a fundamental problem for networks, serving as a tool for avoiding conflicts via symmetry breaking, for example, avoiding multiple computer processes simultaneou…
cs.DS2025
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…