Skip to main content

Research Repository

Advanced Search

Outputs (122)

Brief Announcement: Amnesiac Flooding: Easy to Break, Hard to Escape (2025)
Presentation / Conference Contribution
Austin, H., Gadouleau, M., Mertzios, G. B., & Trehan, A. (2025, June). Brief Announcement: Amnesiac Flooding: Easy to Break, Hard to Escape. Presented at ACM Principles of Distributed Computing (PODC) 2025, Huatulco, Mexico

Broadcast is a central problem in distributed computing. Recently, Hussak and Trehan [PODC'19/DC'23] proposed a stateless broadcasting protocol (Amnesiac Flooding), which was surprisingly proven to terminate in asymptotically optimal time (linear in... Read More about Brief Announcement: Amnesiac Flooding: Easy to Break, Hard to Escape.

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.