13 citations · 38 across the 17 of their papers we have counts for
20 papers
Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation
Louis Dublois, Michael Lampis, Vangelis Th. Paschos
An upper dominating set is a minimal dominating set in a graph. In the \textsc{Upper Dominating Set} problem, the goal is to find an upper dominating set of maximum size. We study…
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…
A polynomial time approximation schema for maximum k-vertex cover in bipartite graphs
Vangelis Th. Paschos
The paper presents a polynomial time approximation schema for the edge-weighted version of maximum k-vertex cover problem in bipartite graphs.
Average-case complexity of a branch-and-bound algorithm for min dominating set
Tom Denat, Ararat Harutyunyan, Vangelis Th. Paschos
The average-case complexity of a branch-and-bound algorithms for Minimum Dominating Set problem in random graphs in the G(n,p) model is studied. We identify phase transitions betwe…
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…