13 citations · 46 across the 31 of their papers we have counts for
5 papers · 1 filter
New Algorithms for Mixed Dominating Set
Louis Dublois, Michael Lampis, Vangelis Th. Paschos
A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \te…
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…
Independent Set Reconfiguration Parameterized by Modular-Width
Rémy Belmonte, Tesshu Hanaka, Michael Lampis +2
Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for g…
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…