The complexity of computing optimum labelings for temporal connectivity
(2024)
Journal Article
Outputs (5)
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle (2024)
Journal Article
Temporal Graph Realization from Fastest Paths (2024)
Presentation / Conference Contribution
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.
Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs (2024)
Presentation / Conference Contribution
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.
Fast parameterized preprocessing for polynomial-time solvable graph problems (2024)
Journal Article