43 citations · 187 across the 40 of their papers we have counts for
56 papers
Enumerating Inclusion-Maximal Arithmetic Progressions
Brian Bemman, Maximilien Gadouleau, Oliver W. Gnilke +1
We present a simple enumeration algorithm for solving a problem from mathematical and computational music analysi…
Round-Delayed Amnesiac Flooding
Oluwatobi Alafin, George B. Mertzios, Paul G. Spirakis
We present a comprehensive analysis of Round-Delayed Amnesiac Flooding (RDAF), a variant of Amnesiac Flooding that introduces round-based asynchrony through adversarial delays. We…
Sharp Thresholds for Temporal Motifs and Doubling Time in Random Temporal Graphs
Henry Austin, George B. Mertzios, Paul G. Spirakis
In this paper we study two natural models of random temporal graphs. In the first, the continuous model, each edge is assigned labels, each drawn uniformly at random from…
Maintaining Bipartite Colourings on Temporal Graphs on a Budget
Duncan Adamson, George B. Mertzios, Paul G. Spirakis
Graph colouring is a fundamental problem for networks, serving as a tool for avoiding conflicts via symmetry breaking, for example, avoiding multiple computer processes simultaneou…
Temporal Graph Realization With Bounded Stretch
George B. Mertzios, Hendrik Molter, Nils Morawietz +1
A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first time steps, and then it reappears recurrently every time s…
Amnesiac Flooding: Easy to break, hard to escape
Henry Austin, Maximilien Gadouleau, George B. Mertzios +1
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 surpr…
NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
David L. Fairbairn, George B. Mertzios, Norbert Peyerimhoff
The -CombDMR problem is that of determining whether an distance matrix can be realised by vertices in some undirected graph with vertices. This problem…
On the existence of -temporal cliques in random simple temporal graphs
George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos +1
We consider random simple temporal graphs in which every edge of the complete graph appears once within the time interval [0,1] independently and uniformly at random. Our mai…
Realizing temporal transportation trees
George B. Mertzios, Hendrik Molter, Nils Morawietz +1
In this paper, we study the complexity of the periodic temporal graph realization problem with respect to upper bounds on the fastest path durations among its vertices. This constr…
Payment Scheduling in the Interval Debt Model
Tom Friedetzky, David C. Kutner, George B. Mertzios +2
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 cons…
Graphs with minimum fractional domatic number
Maximilien Gadouleau, Nathaniel Harms, George B. Mertzios +1
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…
Realizing temporal graphs from fastest travel times
Nina Klobas, George B. Mertzios, Hendrik Molter +1
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 gra…
The Complexity of Temporal Vertex Cover in Small-Degree Graphs
Thekla Hamm, Nina Klobas, George B. Mertzios +1
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(o…
The complexity of computing optimum labelings for temporal connectivity
Nina Klobas, George B. Mertzios, Hendrik Molter +1
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 to every other vertex . In…
The Complexity of Growing a Graph
George B. Mertzios, Othon Michail, George Skretas +2
We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called \emph{slots}. In every slot, the graph grow…
Interference-free Walks in Time: Temporally Disjoint Paths
Nina Klobas, George B. Mertzios, Hendrik Molter +2
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 pa…
The Complexity of Transitively Orienting Temporal Graphs
George B. Mertzios, Hendrik Molter, Malte Renken +2
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. increa…
Equitable Scheduling on a Single Machine
Klaus Heeger, Danny Hermelin, George B. Mertzios +3
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 generalizati…
Matching in Stochastically Evolving Graphs
Eleni C. Akrida, Argyrios Deligkas, George B. Mertzios +2
This paper studies the maximum cardinality matching problem in stochastically evolving graphs. We formally define the arrival-departure model with stochastic departures. There, a g…
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis +1
In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph and a Hamiltonian cycle of , how can we compute a second Hamiltonian…
Linear Programming Complementation
Maximilien Gadouleau, George B. Mertzios, Viktor Zamaraev
In this paper we introduce a new operation for Linear Programming (LP), called LP complementation, which resembles many properties of LP duality. Given a maximisation (resp.~minimi…
Computing Maximum Matchings in Temporal Graphs
George B. Mertzios, Hendrik Molter, Rolf Niedermeier +2
Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph , a temporal graph is represented by assigning a set of integ…
How fast can we reach a target vertex in stochastic temporal graphs?
Eleni C. Akrida, George B. Mertzios, Sotiris Nikoletseas +3
Temporal graphs are used to abstractly model real-life networks that are inherently dynamic in nature. Given a static underlying graph , a temporal graph on is a seque…
Sliding Window Temporal Graph Coloring
George B. Mertzios, Hendrik Molter, Viktor Zamaraev
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 matchin…