13 citations · 46 across the 31 of their papers we have counts for
Showing 2009Show all
3 papers · 1 filter
cs.LO2009
Parameterized Modal Satisfiability
Antonis Achilleos, Michael Lampis, Valia Mitsou
We investigate the parameterized computational complexity of the satisfiability problem for modal logic and attempt to pinpoint relevant structural parameters which cause the probl…
cs.DS2009
Algorithmic Meta-Theorems for Graphs of Bounded Vertex Cover
Michael Lampis
Possibly the most famous algorithmic meta-theorem is Courcelle's theorem, which states that all MSO-expressible graph properties are decidable in linear time for graphs of bounded…
cs.CC2009
Vertex Cover Problem Parameterized Above and Below Tight Bounds
Gregory Gutin, Eun Jung Kim, Michael Lampis +1
We study the well-known Vertex Cover problem parameterized above and below tight bounds. We show that two of the parameterizations (both were suggested by Mahajan, Raman and Sikdar…