3 citations · 3 across the 3 of their papers we have counts for
3 papers
cs.DM2012★ 3 cited
Local Improvement Gives Better Expanders
Michael Lampis
It has long been known that random regular graphs are with high probability good expanders. This was first established in the 1980s by Bollobás by directly calculating the probabil…
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…