9 citations · 17 across the 4 of their papers we have counts for
6 papers · 1 filter
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…
Parameterized Orientable Deletion
Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis +2
A graph is -orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most . -orientability is a well-studied concept with close…
Structurally Parameterized d-Scattered Set
Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos
In -Scattered Set we are given an (edge-weighted) graph and are asked to select at least vertices, so that the distance between any pair is at least , thus generalizing I…
Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center
Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos
In -Center we are given a (possibly edge-weighted) graph and are asked to select at most vertices (centers), so that all other vertices are at distance at most from…