13 citations · 46 across the 31 of their papers we have counts for
4 papers · 2 filters
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…