All Outputs (50)

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

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.

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

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.

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.

Interference-free walks in time: temporally disjoint paths (2021)
Presentation / Conference Contribution
Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2021, August). Interference-free walks in time: temporally disjoint paths. Presented at 30th International Joint Conference on Artificial Intelligence (IJCAI-21), Montreal, Quebec

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.

The complexity of transitively orienting temporal graphs (2021)
Presentation / Conference Contribution
Mertzios, G., Molter, H., Renken, M., Spirakis, P., & Zschoche, P. (2021, August). The complexity of transitively orienting temporal graphs. Presented at 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Tallinn, Estonia

In a temporal network with discrete time-labels on its edges, entities and information can only “flow” along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless,... Read More about The complexity of transitively orienting temporal graphs.

Equitable scheduling on a single machine (2021)
Presentation / Conference Contribution
Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2021, February). Equitable scheduling on a single machine. Presented at 35th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, Canada

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

Exact and approximate algorithms for computing a second Hamiltonian cycle (2020)
Presentation / Conference Contribution
Deligkas, A., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020, December). Exact and approximate algorithms for computing a second Hamiltonian cycle. Presented at MFCS 2020 (International Symposium on Mathematical Foundations of Computer Science), Prague, Czech Republic

A classic result by Stockmeyer [Stockmeyer, 1974] gives a non-elementary lower bound to the emptiness problem for star-free generalized regular expressions. This result is intimately connected to the satisfiability problem for interval temporal logic... Read More about Exact and approximate algorithms for computing a second Hamiltonian cycle.

Computing maximum matchings in temporal graphs (2020)
Presentation / Conference Contribution
Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2020, December). Computing maximum matchings in temporal graphs. Presented at 37th International Symposium on Theoretical Aspects of Computer Science (STACS), Montpellier, France

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.

Deleting edges to restrict the size of an epidemic in temporal networks (2019)
Presentation / Conference Contribution
Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2019, August). Deleting edges to restrict the size of an epidemic in temporal networks. Presented at 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aachen, Germany

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information or behaviour spread over social networks, biological diseases spreading over contact or trade networks, and the potential flow of good... Read More about Deleting edges to restrict the size of an epidemic in temporal networks.

How fast can we reach a target vertex in stochastic temporal graphs? (2019)
Presentation / Conference Contribution
Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Christoforos, R., Spirakis, P. G., & Zamaraev, V. (2019, July). How fast can we reach a target vertex in stochastic temporal graphs?. Presented at 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece

Temporal graphs are used to abstractly model real-life networks that are inherently dynamic in nature, in the sense that the network structure undergoes discrete changes over time. Given a static underlying graph G=(V,E), a temporal graph on G is a s... Read More about How fast can we reach a target vertex in stochastic temporal graphs?.

Sliding Window Temporal Graph Coloring (2019)
Presentation / Conference Contribution
Mertzios, G., Molter, H., & Zamaraev, V. (2023, January). Sliding Window Temporal Graph Coloring. Presented at 33rd AAAI Conference on Artificial Intelligence (AAAI 2019)., Honolulu, Hawaii, USA

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which... Read More about Sliding Window Temporal Graph Coloring.

The temporal explorer who returns to the base (2019)
Presentation / Conference Contribution
Akrida, E., Mertzios, G., & Spirakis, P. (2019, December). The temporal explorer who returns to the base. Presented at 11th International Conference on Algorithms and Complexity (CIAC 2019), Rome, Italy

In this paper we study the problem of exploring a temporal graph (i.e. a graph that changes over time), in the fundamental case where the underlying static graph is a star on n vertices. The aim of the exploration problem in a temporal star is to fin... Read More about The temporal explorer who returns to the base.

Temporal vertex cover with a sliding time window (2018)
Presentation / Conference Contribution
Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2018, July). Temporal vertex cover with a sliding time window. Presented at 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)., Prague, Czech Republic

Modern, inherently dynamic systems are usually characterized by a network structure, i.e. an underlying graph topology, which is subject to discrete changes over time. Given a static underlying graph G, a temporal graph can be represented via an assi... Read More about Temporal vertex cover with a sliding time window.

Binary search in graphs revisited (2017)
Presentation / Conference Contribution
Deligkas, A., Mertzios, G., & Spirakis, P. (2017, August). Binary search in graphs revisited. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), Aalborg, Denmark

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by [Emamjomeh-Zadeh et... Read More about Binary search in graphs revisited.