2 citations · 6 across the 22 of their papers we have counts for
7 papers · 1 filter
A Logic for Minor-Free Graph Classes: Model Checking, Dependence, and Combinatorial Reconfiguration
Nikolas Mählmann, Patrice {Ossona de Mendez}, Nicole Schirrmacher +4
We introduce \emph{sub-connectivity logic}, denoted by , an extension of first-order logic for graphs with a specified set of admissible edges. Its additional…
Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz +3
Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions o…
Low rank MSO
Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski +2
We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restrict…
Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos
Given a graph and a vertex set , the annotated treewidth tw of in is the maximum treewidth of an -rooted minor of , i.e., a minor where the model of…
Elementary first-order model checking for sparse graphs
Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski +2
It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, S…
Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis +2
Disjoint-paths logic, denoted +, extends first-order logic () with atomic predicates , expressing…
Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos
The disjoint paths logic, FOL+DP, is an extension of First-Order Logic (FOL) with the extra atomic predicate expressing the existence of in…