Logic, graphs, and algorithms

MaRDI QIDQ3086928zbMATH OpenFDO

Authors Martin Grohe

Publication date 30 March 2011

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Decidability of theories and sets of sentences (03B25) General topics in the theory of algorithms (68W01)

Recommendations

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

Cited in

(32)

• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• Compactors for parameterized counting problems
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
• A Retrospective on (Meta) Kernelization
• Feferman-vaught decompositions for prefix classes of first order logic
• Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
• First-Order Model-Checking in Random Graphs and Complex Networks
• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• Courcelle's theorem -- a game-theoretic approach
• Algorithmic meta theorems for circuit classes of constant and logarithmic depth
• Monadic second-order model-checking on decomposable matroids
• Data-compression for parametrized counting problems on sparse graphs
• A SAT approach to branchwidth
• The parameterized space complexity of model-checking bounded variable first-order logic
• Algorithmic meta-theorems for restrictions of treewidth
• Algorithmic meta-theorems for restrictions of treewidth
• Kernelization of cycle packing with relaxed disjointness constraints
• Efficient First-Order Model-Checking Using Short Labels
• A Practical Approach to Courcelle's Theorem
• Algorithmic meta-theorems
• Confronting intractability via parameters
• Gaifman normal forms for counting extensions of first-order logic
• An algorithmic meta-theorem for graph modification to planarity and FOL
• First-order Logic with Connectivity Operators
• Compact labelings for efficient first-order model-checking
• An approval-based model for single-step liquid democracy
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Courcelle's theorem for triangulations
• Large Induced Subgraphs via Triangulations and CMSO
• Algorithmic meta theorems for sparse graph classes
• Methods for algorithmic meta theorems

This page was built for publication: Logic, graphs, and algorithms

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