5 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…
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…
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…
On the existence of -temporal cliques in random simple temporal graphs
George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos +1
We consider random simple temporal graphs in which every edge of the complete graph appears once within the time interval [0,1] independently and uniformly at random. Our mai…
On the existence of highly organized communities in networks of locally interacting agents
V. Liagkou, P. E. Nastou, P. Spirakis +1
In this paper we investigate phenomena of spontaneous emergence or purposeful formation of highly organized structures in networks of related agents. We show that the formation of…