23 citations · 110 across the 25 of their papers we have counts for
33 papers
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Édouard Bonnet, Jan Dreier, Jakub Gajarský +4
We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpret…
Excluding a Planar Matching Minor in Bipartite Graphs
Archontia C Giannopoulou, Stephan Kreutzer, Sebastian Wiederrecht
Matching minors are a specialisation of minors fit for the study of graph with perfect matchings. The notion of matching minors has been used to give a structural description of bi…
The canonical directed tree decomposition and its applications to the directed disjoint paths problem
Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
The canonical tree-decomposition theorem, given by Robertson and Seymour in their seminal graph minors series, turns out to be one of the most important tool in structural and algo…
Differential games, locality and model checking for FO logic of graphs
Jakub Gajarský, Maximilian Gorsky, Stephan Kreutzer
We introduce differential games for FO logic of graphs, a variant of Ehrenfeucht-Fraïssé games in which the game is played on only one graph and the moves of both players restricte…
A half-integral Erdős-Pósa theorem for directed odd cycles
Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon +1
We prove that there exists a function such that every directed graph contains either directed odd cycles where every vertex of is c…
Model-Checking on Ordered Structures
Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi +6
We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on…