13 citations · 46 across the 31 of their papers we have counts for
3 papers · 2 filters
Improved (In-)Approximability Bounds for d-Scattered Set
Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos
In the -Scattered Set problem we are asked to select at least vertices of a given graph, so that the distance between any pair is at least . We study the problem's (in-)a…
New Results on Directed Edge Dominating Set
Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis +2
We study a family of generalizations of Edge Dominating Set on directed graphs called Directed -Edge Dominating Set. In this problem an arc is said to dominate itsel…
Parameterized Complexity of Safe Set
Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis +3
In this paper we study the problem of finding a small safe set in a graph , i.e. a non-empty set of vertices such that no connected component of is adjacent to a larg…