Publications (28)
Complexity and Approximability of Parameterized MAX-CSPs
Holger Dell, Eun Jung Kim, Michael Lampis +2
Vertex Cover Problem Parameterized Above and Below Tight Bounds
Gregory Gutin, Eun Jung Kim, Michael Lampis +1
Parameterized Modal Satisfiability
Antonis Achilleos, Michael Lampis, Valia Mitsou
QBF as an Alternative to Courcelle's Theorem
Michael Lampis, Stefan Mengel, Valia Mitsou
Closing a Gap in the Complexity of Refinement Modal Logic
Antonis Achilleos, Michael Lampis
Finer Tight Bounds for Coloring on Clique-Width
Michael Lampis
Token Sliding on Split Graphs
Rémy Belmonte, Eun Jung Kim, Michael Lampis +3
Parameterized Edge Hamiltonicity
Michael Lampis, Kazuhisa Makino, Valia Mitsou +1
Parameterized Approximation Schemes using Graph Widths
Michael Lampis
Improved Inapproximability for TSP
Michael Lampis
Algorithmic Aspects of Upper Domination
Cristina Bazgan, Ljiljana Brankovic, Katrin Casel +6
Time-Approximation Trade-offs for Inapproximable Problems
Ãdouard Bonnet, Michael Lampis, Vangelis Th. Paschos
Local Improvement Gives Better Expanders
Michael Lampis
Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center
Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos
Structurally Parameterized d-Scattered Set
Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos
New Inapproximability Bounds for TSP
Marek Karpinski, Michael Lampis, Richard Schmied
Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse
Dimitris Fotakis, Michael Lampis, Vangelis Th. Paschos
Parameterized (Approximate) Defective Coloring
Rémy Belmonte, Michael Lampis, Valia Mitsou
Scrabble is PSPACE-Complete
Michael Lampis, Valia Mitsou, Karolina SoÅtys
Model Checking Lower Bounds for Simple Graphs
Michael Lampis
Independent Set Reconfiguration Parameterized by Modular-Width
Rémy Belmonte, Tesshu Hanaka, Michael Lampis +2
Parameterized Complexity of Safe Set
Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis +3
The Computational Complexity of the Game of Set and its Theoretical Applications
Michael Lampis, Valia Mitsou
Algorithmic Meta-Theorems for Graphs of Bounded Vertex Cover
Michael Lampis
Parameterized Algorithms for Modular-Width
Jakub Gajarský, Michael Lampis, Sebastian Ordyniak
On the Parameterized Complexity of Red-Blue Points Separation
Ãdouard Bonnet, Panos Giannopoulos, Michael Lampis
Maximum Independent Sets in Subcubic Graphs: New Results
Ararat Harutyunyan, Michael Lampis, Vadim Lozin +1
How Bad is the Freedom to Flood-It?
Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi +2