13 citations · 46 across the 31 of their papers we have counts for
5 papers · 1 filter
Filling Crosswords is Very Hard
Laurent Gourvès, Ararat Harutyunyan, Michael Lampis +1
We revisit a classical crossword filling puzzle which already appeared in Garey\&Jonhson's book. We are given a grid with vertical and horizontal slots and a dictionary with $m…
Fine-grained Meta-Theorems for Vertex Integrity
Michael Lampis, Valia Mitsou
Vertex Integrity is a graph measure which sits squarely between two more well-studied notions, namely vertex cover and tree-depth, and that has recently gained attention as a struc…
Minimum Stable Cut and Treewidth
Michael Lampis
A stable or locally-optimal cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. In this paper we study Minimum Stable Cut, the problem…
Determining a Slater Winner is Complete for Parallel Access to NP
Michael Lampis
We consider the complexity of deciding the winner of an election under the Slater rule. In this setting we are given a tournament , where the vertices of V represent ca…
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…