4 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…
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…
First-Order Logic with Connectivity Operators
Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny
First-order logic (FO) can express many algorithmic problems on graphs, such as the independent set and dominating set problem, parameterized by solution size. On the other hand, F…