Skip to main content

Research Repository

Advanced Search

Dr George Mertzios' Outputs (120)

NP-completeness of the combinatorial distance matrix realisation problem (2025)
Presentation / Conference Contribution
Fairbairn, D., Mertzios, G., & Peyerimhoff, N. (2025, December). NP-completeness of the combinatorial distance matrix realisation problem. Presented at 14th International Symposium on Algorithms and Complexity (CIAC 2025), Rome, Italy

The k-CombDMR problem is that of determining whether an n×n distance matrix can be realised by n vertices in some undirected graph with n+k vertices. This problem has a simple solution in the case k=0. In this paper we show that this problem is polyn... Read More about NP-completeness of the combinatorial distance matrix realisation problem.

The threshold of existence of δ-temporal cliques in random simple temporal graphs (2024)
Presentation / Conference Contribution
Mertzios, G. B., 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

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 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.

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.

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.

Graphs with minimum fractional domatic number (2023)
Journal Article
Gadouleau, M., Harms, N., Mertzios, G. B., & Zamaraev, V. (2024). Graphs with minimum fractional domatic number. Discrete Applied Mathematics, 343, 140-148. https://doi.org/10.1016/j.dam.2023.10.020

The domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant of this notion. Graphs with fractional domatic number 1 are exactly th... Read More about Graphs with minimum fractional domatic number.

Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (2023)
Presentation / Conference Contribution
Klobas, N., Mertzios, G. B., & Spirakis, P. G. (2023, August). Sliding into the Future: Investigating Sliding Windows in Temporal Graphs. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France

Computing maximum matchings in temporal graphs (2023)
Journal Article
Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2023). Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences, 137, 1-19. https://doi.org/10.1016/j.jcss.2023.04.005

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps... Read More about Computing maximum matchings in temporal graphs.

Payment scheduling in the Interval Debt Model (2023)
Presentation / Conference Contribution
Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023, January). Payment scheduling in the Interval Debt Model. Presented at 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023), Novy Smokovec, Slovakia

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

The complexity of growing a graph (2022)
Presentation / Conference Contribution
Mertzios, G., Michail, O., Skretas, G., Spirakis, P., & Theofilatos, M. (2022, September). The complexity of growing a graph. Presented at 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS 2022), Potsdam, Germany

We study a new algorithmic process of graph growth. The process starts from a single initial vertex u0 and operates in discrete timesteps, called slots. In every slot t ≥ 1, the process updates the current graph instance to generate the next graph in... Read More about The complexity of growing a graph.

Interference-free walks in time: Temporally disjoint paths (2022)
Journal Article
Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2022). Interference-free walks in time: Temporally disjoint paths. Autonomous Agents and Multi-Agent Systems, 37, Article 1. https://doi.org/10.1007/s10458-022-09583-5

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing tim... Read More about Interference-free walks in time: Temporally disjoint paths.

Equitable scheduling on a single machine (2022)
Journal Article
Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2023). Equitable scheduling on a single machine. Journal of Scheduling, 26(2), 209-225. https://doi.org/10.1007/s10951-022-00754-6

We introduce a natural but seemingly yet unstudied variant of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. The novelty of our new variant lies in simultaneously considering several instances of the pr... Read More about Equitable scheduling on a single machine.

The complexity of computing optimum labelings for temporal connectivity (2022)
Presentation / Conference Contribution
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2022, August). The complexity of computing optimum labelings for temporal connectivity. Presented at 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Vienna, Austria

A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally c... Read More about The complexity of computing optimum labelings for temporal connectivity.

The complexity of temporal vertex cover in small-degree graphs (2022)
Presentation / Conference Contribution
Hamm, T., Klobas, N., Mertzios, G., & Spirakis, P. (2023, February). The complexity of temporal vertex cover in small-degree graphs. Presented at 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vancouver, BC

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or ∆- TVC for time-windows of a fixed-length ∆) have been established... Read More about The complexity of temporal vertex cover in small-degree graphs.