37 citations · 102 across the 14 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.DS2013
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…
cs.DS2013★ 13 cited
Kernelization Using Structural Parameters on Sparse Graph Classes
Jakub Gajarský, Petr Hliněný, Jan Obdržálek +5
Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, meta-theorems for linear kernels exist on graphs…
cs.DM2013★ 16 cited
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…