Algorithmic meta-theorems

MaRDI QIDQ3172385zbMATH OpenFDO

Authors Stephan Kreutzer

Publication date 5 October 2011

zbMATH Keywords

survey paper

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05) Graph minors (05C83) Decidability of theories and sets of sentences (03B25) General topics in the theory of algorithms (68W01)

Recommendations

• Logic, graphs, and algorithms
• Methods for algorithmic meta theorems
• Algorithmic meta theorems for sparse graph classes
• Algorithmic Meta-theorems
• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes

Cited in

(28)

• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Coloring and covering nowhere dense graphs
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Algorithmic Meta-theorems
• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• On ultralimits of sparse graph classes
• Recovering sparse graphs
• Compound logics for modification problems
• On the weak 2-coloring number of planar graphs
• Logic, graphs, and algorithms
• An algorithmic meta-theorem for graph modification to planarity and FOL
• Complexity framework for forbidden subgraphs. I: The framework
• Colouring and covering nowhere dense graphs
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Extended MSO model checking via small vertex integrity
• An algorithmic meta-theorem for graph modification to planarity and FOL
• On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus
• Computations by fly-automata beyond monadic second-order logic
• The Complexity of Decomposing Modal and First-Order Theories
• On the Parameterised Intractability of Monadic Second-Order Logic
• Model checking on interpretations of classes of bounded local cliquewidth
• Distributed model checking on graphs of bounded treedepth
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• Large Induced Subgraphs via Triangulations and CMSO
• Algorithmic Pirogov-Sinai theory
• Algorithmic meta theorems for sparse graph classes
• Methods for algorithmic meta theorems

This page was built for publication: Algorithmic meta-theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3172385)