Skip to main content

Research Repository

Advanced Search

Outputs (125)

Round-asynchronous amnesiac flooding (2025)
Presentation / Conference Contribution
Alafin, O., Mertzios, G., & Spirakis, P. (2025, September). Round-asynchronous amnesiac flooding. Presented at International Symposium on Algorithmics of Wireless Networks (ALGOWIN 2025), Warsaw, Poland

Temporal graph realization with bounded stretch (2025)
Presentation / Conference Contribution
Mertzios, G., Molter, H., Morawietz, N., & Spirakis, P. (2025, August). Temporal graph realization with bounded stretch. Presented at Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), Warsaw, Poland

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.

Realizing temporal transportation trees (2025)
Presentation / Conference Contribution
Mertzios, G., Molter, H., Morawietz, N., & Spirakis, P. (2025, June). Realizing temporal transportation trees. Presented at 51st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2025), Otzenhausen, Germany

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.