Courcelle's theorem -- a game-theoretic approach
From MaRDI portal
Publication:408375
DOI10.1016/J.DISOPT.2011.06.001zbMATH Open1235.68103OpenAlexW2963886128MaRDI QIDQ408375FDOQ408375
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
Recommendations
- A Practical Approach to Courcelle's Theorem
- Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Evaluation of an MSO-Solver
- Monadic Datalog over finite structures of bounded treewidth
Applications of game theory (91A80) Specification and verification (program logics, model checking, etc.) (68Q60)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Linear time solvable optimization problems on graphs of bounded clique-width
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Easy problems for tree-decomposable graphs
- Complexity of Finding Embeddings in a k-Tree
- Title not available (Why is that?)
- Title not available (Why is that?)
- Query evaluation via tree-decompositions
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Title not available (Why is that?)
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Title not available (Why is that?)
- Treewidth computations. I: Upper bounds
- The complexity of first-order and monadic second-order logic revisited
- Special tree-width and the verification of monadic second-order graph properties
- On the model-checking of monadic second-order formulas with edge set quantifications
- Monadic second-order evaluations on tree-decomposable graphs
- A technique of state space search based on unfolding
- Title not available (Why is that?)
- Tree acceptors and some of their applications
- Title not available (Why is that?)
- The first order properties of products of algebraic systems
- Necessary edges in \(k\)-chordalisations of graphs
- On converting CNF to DNF
- Easy instances for model checking
- Monadic datalog over finite structures of bounded treewidth
- Title not available (Why is that?)
- Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
- New Algorithm for Weak Monadic Second-Order Logic on Inductive Structures
- Modest theory of short chains. I
- Title not available (Why is that?)
- Treewidth computations. II. Lower bounds
- Algorithmic uses of the Feferman-Vaught theorem
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
Cited In (20)
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Efficient Problem Solving on Tree Decompositions Using Binary Decision Diagrams
- Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
- On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity
- Fixed-Parameter Tractability of Treewidth and Pathwidth
- Practical access to dynamic programming on tree decompositions
- Title not available (Why is that?)
- Graph Minors and Parameterized Algorithm Design
- The Cournot-Theocharis problem reconsidered
- DynASP2.5: Dynamic Programming on Tree Decompositions in Action
- Confronting intractability via parameters
- Digraph width measures in parameterized algorithmics
- Practical Access to Dynamic Programming on Tree Decompositions
- Computations by fly-automata beyond monadic second-order logic
- Title not available (Why is that?)
- Courcelle's theorem for triangulations
- A uniform Tauberian theorem in dynamic games
- Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
- A Characterization of Game-Theoretic Solutions which Lead to Impossibility Theorems
- Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
Uses Software
This page was built for publication: Courcelle's theorem -- a game-theoretic approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q408375)
