24 citations · 124 across the 75 of their papers we have counts for
3 papers · 1 filter
Expanding the expressive power of Monadic Second-Order logic on restricted graph classes
Robert Ganian, Jan Obdržálek
We combine integer linear programming and recent advances in Monadic Second-Order model checking to obtain two new algorithmic meta-theorems for graphs of bounded vertex-cover. The…
Meta-Kernelization with Structural Parameters
Robert Ganian, Friedrich Slivovsky, Stefan Szeider
Meta-kernelization theorems are general results that provide polynomial kernels for large classes of parameterized problems. The known meta-kernelization theorems, in particular th…
FO Model Checking of Interval Graphs
Robert Ganian, Petr Hlineny, Daniel Kral +3
We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that…