43 citations · 187 across the 40 of their papers we have counts for
4 papers · 1 filter
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…
Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity
Florent Foucaud, George B. Mertzios, Reza Naserasr +2
We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted IDENTIFYING CODE, (OPEN) LOCATING-DOMINATING SET and METR…
Intersection Graphs of L-Shapes and Segments in the Plane
Stefan Felsner, Kolja Knauer, George B. Mertzios +1
An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: L, Γ, LE{} and \eeG. A -bend path is a simple path in the pl…
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.