43 citations · 187 across the 40 of their papers we have counts for
6 papers · 1 filter
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…
The temporal explorer who returns to the base
Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis
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. The aim…
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…
Temporal Vertex Cover with a Sliding Time Window
Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis +1
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 stat…
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…