Accueil

Michael Lampis

  1. Algorithmic Meta-Theorems for Graphs of Bounded Vertex Cover.

    Tue, 10/06/2009 - 17:01 — SomNambul
    Authors: Michael Lampis
    Subjects: Computational Complexity
    Abstract

    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 treewidth. Unfortunately, the running time's
    dependence on the MSO formula describing the problem is in general an
    exponential tower of unbounded height, and there exist lower bounds proving
    that this cannot be improved.

  2. Vertex Cover Problem Parameterized Above and Below Tight Bounds.

    Mon, 08/31/2009 - 17:16 — SomNambul
    Authors: Gregory Gutin, Eun Jung Kim, Michael Lampis, Valia Mitsou
    Subjects: Computational Complexity
    Abstract

    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, J. Computer and System Sciences, 75(2):137--153,
    2009) are fixed-parameter tractable and two other parameterizations are
    W[1]-hard (one of them is, in fact, W[2]-hard).

Math-arch

Syndicate content