9 papers
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…
Enumerating Inclusion-Maximal Arithmetic Progressions
Brian Bemman, Maximilien Gadouleau, Oliver W. Gnilke +1
We present a simple enumeration algorithm for solving a problem from mathematical and computational music analysi…
Round-Delayed Amnesiac Flooding
Oluwatobi Alafin, George B. Mertzios, Paul G. Spirakis
We present a comprehensive analysis of Round-Delayed Amnesiac Flooding (RDAF), a variant of Amnesiac Flooding that introduces round-based asynchrony through adversarial delays. We…
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…
Amnesiac Flooding: Easy to break, hard to escape
Henry Austin, Maximilien Gadouleau, George B. Mertzios +1
Broadcast is a central problem in distributed computing. Recently, Hussak and Trehan [PODC'19/DC'23] proposed a stateless broadcasting protocol (Amnesiac Flooding), which was surpr…
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…