Logic, graphs, and algorithms
From MaRDI portal
Publication:3086928
zbMATH Open1244.03053MaRDI QIDQ3086928FDOQ3086928
Authors: Martin Grohe 
Publication date: 30 March 2011
Recommendations
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)
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
- Feferman-vaught decompositions for prefix classes of first order logic
- A Retrospective on (Meta) Kernelization
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
- First-Order Model-Checking in Random Graphs and Complex Networks
- A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
- Algorithmic meta theorems for circuit classes of constant and logarithmic depth
- Courcelle's theorem -- a game-theoretic approach
- 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
- An approval-based model for single-step liquid democracy
- Compact labelings for efficient first-order model-checking
- 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)
