43 citations · 187 across the 40 of their papers we have counts for
4 papers · 1 filter
Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds
Florent Foucaud, George B. Mertzios, Reza Naserasr +2
We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets of an interval or a permutation graph. In these problems, one asks…
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…
The complexity of optimal design of temporally connected graphs
Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios +1
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of vertices, where each edge has an associated se…
Temporal Network Optimization Subject to Connectivity Constraints
George B. Mertzios, Othon Michail, Paul G. Spirakis
In this work we consider \emph{temporal networks}, i.e. networks defined by a \emph{labeling} assigning to each edge of an \emph{underlying graph} a set of \emph{discrete}…