Courcelle's theorem -- a game-theoretic approach
From MaRDI portal
Publication:408375
DOI10.1016/j.disopt.2011.06.001zbMath1235.68103OpenAlexW2963886128MaRDI QIDQ408375
Peter Rossmanith, Joachim Kneis, Alexander Langer
Publication date: 5 April 2012
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2011.06.001
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (16)
On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity ⋮ Efficient Problem Solving on Tree Decompositions Using Binary Decision Diagrams ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Courcelle's theorem for triangulations ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Digraph width measures in parameterized algorithmics ⋮ Unnamed Item ⋮ Confronting intractability via parameters ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Practical Access to Dynamic Programming on Tree Decompositions ⋮ Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory ⋮ Fly-automata for checking \(\mathrm{MSO}_2\) graph properties ⋮ Practical access to dynamic programming on tree decompositions ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ DynASP2.5: Dynamic Programming on Tree Decompositions in Action
Uses Software
Cites Work
- On the model-checking of monadic second-order formulas with edge set quantifications
- Treewidth computations. II. Lower bounds
- Algorithmic uses of the Feferman-Vaught theorem
- Monadic second-order evaluations on tree-decomposable graphs
- Treewidth computations. I: Upper bounds
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- A partial k-arboretum of graphs with bounded treewidth
- A technique of state space search based on unfolding
- Necessary edges in \(k\)-chordalisations of graphs
- The complexity of first-order and monadic second-order logic revisited
- Linear time solvable optimization problems on graphs of bounded clique-width
- Parametrized complexity theory.
- Tree acceptors and some of their applications
- On converting CNF to DNF
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Monadic datalog over finite structures of bounded treewidth
- The first order properties of products of algebraic systems
- Easy problems for tree-decomposable graphs
- Query evaluation via tree-decompositions
- Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
- New Algorithm for Weak Monadic Second-Order Logic on Inductive Structures
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Modest theory of short chains. I
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Generalized finite automata theory with an application to a decision problem of second-order logic
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Courcelle's theorem -- a game-theoretic approach
