13 citations · 46 across the 31 of their papers we have counts for
6 papers · 1 filter
Parameterized Approximation Schemes using Graph Widths
Michael Lampis
Combining the techniques of approximation algorithms and parameterized complexity has long been considered a promising research area, but relatively few results are currently known…
The Computational Complexity of the Game of Set and its Theoretical Applications
Michael Lampis, Valia Mitsou
The game of SET is a popular card game in which the objective is to form Sets using cards from a special deck. In this paper we study single- and multi-round variations of this gam…
Closing a Gap in the Complexity of Refinement Modal Logic
Antonis Achilleos, Michael Lampis
Refinement Modal Logic (RML), which was recently introduced by Bozzelli et al., is an extension of classical modal logic which allows one to reason about a changing model. In this…
Parameterized Algorithms for Modular-Width
Jakub Gajarský, Michael Lampis, Sebastian Ordyniak
It is known that a number of natural graph problems which are FPT parameterized by treewidth become W-hard when parameterized by clique-width. It is therefore desirable to find a d…
New Inapproximability Bounds for TSP
Marek Karpinski, Michael Lampis, Richard Schmied
In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now know…
Model Checking Lower Bounds for Simple Graphs
Michael Lampis
A well-known result by Frick and Grohe shows that deciding FO logic on trees involves a parameter dependence that is a tower of exponentials. Though this lower bound is tight for C…