Skip to main content

Research Repository

Advanced Search

All Outputs (8)

Payment Scheduling in the Interval Debt Model (2024)
Journal Article
Stewart, I., Kutner, D., Friedetzky, T., Trehan, A., & Mertzios, G. (2025). Payment Scheduling in the Interval Debt Model. Theoretical Computer Science, 1028, Article 115028. https://doi.org/10.1016/j.tcs.2024.115028

The network-based study of financial systems has received considerable attention in recent years but has seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view and introduc... Read More about Payment Scheduling in the Interval Debt Model.

The complexity of growing a graph (2024)
Journal Article
Mertzios, G., Michail, O., Skretas, G., Spirakis, P. G., & Theofilatos, M. (2025). The complexity of growing a graph. Journal of Computer and System Sciences, 147, Article 103587. https://doi.org/10.1016/j.jcss.2024.103587

We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called slots. In every slot, the graph grows via two operations (i) vertex generation and (ii) edge activation. The proc... Read More about The complexity of growing a graph.

The threshold of existence of δ-temporal cliques in random simple temporal graphs (2024)
Presentation / Conference Contribution
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2024, September). The threshold of existence of δ-temporal cliques in random simple temporal graphs. Presented at The 20th International Symposium on Algorithmics of Wireless Networks (ALGOWIN), Egham, London, United Kingdom

The complexity of computing optimum labelings for temporal connectivity (2024)
Journal Article
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2024). The complexity of computing optimum labelings for temporal connectivity. Journal of Computer and System Sciences, 146, Article 103564. https://doi.org/10.1016/j.jcss.2024.103564

A graph is temporally connected if a strict temporal path exists from every vertex u to every other vertex v. This paper studies temporal design problems for undirected temporally connected graphs. Given a connected undirected graph G, the goal is to... Read More about The complexity of computing optimum labelings for temporal connectivity.

Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle (2024)
Journal Article
Deligkas, A., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2024). Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle. Algorithmica, 86(9), 2766-2785. https://doi.org/10.1007/s00453-024-01238-z

In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C′≠C of G, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if eve... Read More about Approximate and Randomized Algorithms for Computing a Second Hamiltonian Cycle.

Temporal Graph Realization from Fastest Paths (2024)
Presentation / Conference Contribution
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2024, June). Temporal Graph Realization from Fastest Paths. Presented at 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, Patras, Greece

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
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2024, June). Brief Announcement: On the Existence of δ-Temporal Cliques in Random Simple Temporal Graphs. Presented at 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), Patras, Greece

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.