43 citations · 187 across the 40 of their papers we have counts for
25 papers · 1 filter
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…
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…
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…
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…
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…
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…
Lower and Upper Bound for Computing the Size of All Second Neighbourhoods
Gregory Gutin, George B. Mertzios, Felix Reidl
We consider the problem of computing the size of each -neighbourhood for every vertex of a graph. Specifically, we ask whether the size of the closed second neighbourhood can be…
Deleting edges to restrict the size of an epidemic in temporal networks
Jessica Enright, Kitty Meeks, George B. Mertzios +1
Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading ov…
Searching for Maximum Out-Degree Vertices in Tournaments
Gregory Gutin, George B. Mertzios, Felix Reidl
A vertex in a tournament is called a king if for every vertex of there is a directed path from to of length at most 2. It is not hard to show that every ver…
A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
George B. Mertzios, André Nichterlein, Rolf Niedermeier
Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph problems. For general m-edge and n-vertex graphs, it is well-known to be solvab…
Binary Search in Graphs Revisited
Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis
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 bin…
The Power of Data Reduction for Matching
George B. Mertzios, André Nichterlein, Rolf Niedermeier
Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For -edge and -vertex graphs, it is well-known to be solvable…
Graph Editing to a Given Degree Sequence
Petr A. Golovach, George B. Mertzios
We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence, where the aim is to obtain a graph with a given deg…
Strong Bounds for Evolution in Undirected Graphs
George B. Mertzios, Paul G. Spirakis
This work studies the generalized Moran process, as introduced by Lieberman et al. [Nature, 433:312-316, 2005]. We introduce the parameterized notions of selective amplifiers and s…
The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
George B. Mertzios
Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval…
Parameterized Domination in Circle Graphs
Nicolas Bousquet, Daniel Gonçalves, George B. Mertzios +3
A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set…
Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
George B. Mertzios, Paul G. Spirakis
In spite of the extensive studies of the 3-coloring problem with respect to several basic parameters, the complexity status of the 3-coloring problem on graphs with small diameter,…