Skip to main content

Research Repository

Advanced Search

Outputs (4)

Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs (2024)
Conference Proceeding
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2024). Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) (27:1-27:5). https://doi.org/10.4230/LIPIcs.SAND.2024.27

We consider random simple temporal graphs in which every edge of the complete graph K_n appears once within the time interval [0,1] independently and uniformly at random. Our main result is a sharp threshold on the size of any maximum δ-clique (namel... Read More about Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs.

Temporal Graph Realization from Fastest Paths (2024)
Conference Proceeding
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2024). Temporal Graph Realization from Fastest Paths. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) (16:1-16:18). https://doi.org/10.4230/LIPIcs.SAND.2024.16

In this paper we initiate the study of the temporal graph realization problem with respect to the fastest path durations among its vertices, while we focus on periodic temporal graphs. Given an n × n matrix D and a Δ ∈ ℕ, the goal is to construct a Δ... Read More about Temporal Graph Realization from Fastest Paths.