43 citations · 187 across the 40 of their papers we have counts for
11 papers · 1 filter
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…
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…
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…
Kernelization Lower Bounds for Finding Constant-Size Subgraphs
Till Fluschnik, George B. Mertzios, André Nichterlein
Kernelization is an important tool in parameterized algorithmics. Given an input instance accompanied by a parameter, the goal is to compute in polynomial time an equivalent instan…
When can Graph Hyperbolicity be computed in Linear Time?
Till Fluschnik, Christian Komusiewicz, George B. Mertzios +3
Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen int…
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
René van Bevern, Till Fluschnik, George B. Mertzios +3
This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum s-t separators, feed…
Polynomial Fixed-Parameter Algorithms: A Case Study for Longest Path on Interval Graphs
Archontia C. Giannopoulou, George B. Mertzios, Rolf Niedermeier
We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems…
New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs
Archontia C. Giannopoulou, George B. Mertzios
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain amount of overlap without being in conflict. In one of the most natural generalization…
Minimum Bisection is NP-hard on Unit Disk Graphs
Josep Diaz, George B. Mertzios
In this paper we prove that the \textsc{Min-Bisection} problem is NP-hard on \emph{unit disk graphs}, thus solving a longstanding open question.
Approximating Fixation Probabilities in the Generalized Moran Process
Josep Díaz, Leslie Ann Goldberg, George B. Mertzios +3
We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312--316, 2005). A population resides on the vertices of a finite, connected, undirected g…
The Recognition of Tolerance and Bounded Tolerance Graphs
George B. Mertzios, Ignasi Sau, Shmuel Zaks
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been…