Practical algorithms for MSO model-checking on tree-decomposable graphs
From MaRDI portal
Publication:473216
DOI10.1016/j.cosrev.2014.08.001zbMath1302.68184OpenAlexW2158543468MaRDI QIDQ473216
Felix Reidl, Peter Rossmanith, Somnath Sikdar, Alexander Langer
Publication date: 24 November 2014
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2014.08.001
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Complexity of the multilevel critical node problem ⋮ Transforming graph states using single-qubit operations ⋮ The complexity of restricted star colouring ⋮ The firebreak problem ⋮ Unnamed Item ⋮ Computing the clique-width of cactus graphs ⋮ Fly-automata for checking \(\mathrm{MSO}_2\) graph properties ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
Uses Software
Cites Work
- Courcelle's theorem -- a game-theoretic approach
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- On the model-checking of monadic second-order formulas with edge set quantifications
- Sparsity. Graphs, structures, and algorithms
- Treewidth computations. II. Lower bounds
- Algorithmic uses of the Feferman-Vaught theorem
- Monadic second-order evaluations on tree-decomposable graphs
- Boolean-width of graphs
- Testing branch-width
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Treewidth computations. I: Upper bounds
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Graph operations characterizing rank-width
- Graph minors. I. Excluding a forest
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Combinatorial problems on series-parallel graphs
- Graph minors. X: Obstructions to tree-decomposition
- Optimization, approximation, and complexity classes
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- S-functions for graphs
- The polynomial-time hierarchy
- All structured programs have small tree width and good register allocation
- A partial k-arboretum of graphs with bounded treewidth
- Graph searching and a min-max theorem for tree-width
- Regularity and locality in \(k\)-terminal graphs
- Channel assignment on graphs of bounded treewidth
- Which problems have strongly exponential complexity?
- Algorithmic meta-theorems for restrictions of treewidth
- Querying linguistic treebanks with monadic second-order logic in linear time
- On simple characterizations of k-trees
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- The complexity of first-order and monadic second-order logic revisited
- Graph minors. XIII: The disjoint paths problem
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Automata for the verification of monadic second-order graph properties
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Bounded treewidth as a key to tractability of knowledge representation and reasoning
- Handle-rewriting hypergraph grammars
- On nowhere dense graphs
- Parametrized complexity theory.
- Tree-depth, subgraph coloring and homomorphism bounds
- Approximating clique-width and branch-width
- 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
- Model-Checking by Infinite Fly-Automata
- On the Parameterized Intractability of Monadic Second-Order Logic
- Finding Good Decompositions for Dynamic Programming on Dense Graphs
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Exact Algorithms for a Loading Problem with Bounded Clique Width
- Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
- When Trees Grow Low: Shrubs and Fast MSO1
- Monadic datalog over finite structures of bounded treewidth
- Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
- Deciding first-order properties of locally tree-decomposable structures
- The first order properties of products of algebraic systems
- Weak Second‐Order Arithmetic and Finite Automata
- Easy problems for tree-decomposable graphs
- Query evaluation via tree-decompositions
- Clique-Width is NP-Complete
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- On the Parameterised Intractability of Monadic Second-Order Logic
- A Linear Recognition Algorithm for Cographs
- The NP-completeness column: an ongoing guide
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Decision Problems of Finite Automata Design and Related Arithmetics
- The Complexity of Enumeration and Reliability Problems
- Modest theory of short chains. I
- Linear-time computability of combinatorial problems on series-parallel graphs
- Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
- Domino Treewidth
- The Complexity of Translating Logic to Finite Automata
- Deciding First-Order Properties of Nowhere Dense Graphs
- Linear-time computation of optimal subgraphs of decomposable graphs
- (Meta) Kernelization
- Fly-Automata, Their Properties and Applications
- Evaluation of an MSO-Solver
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- The DLV system for knowledge representation and reasoning
- Recontamination does not help to search a graph
- On the Relationship Between Clique-Width and Treewidth
- A combinatorial and logical approach to linear-time computability (extended abstract)
- Directed Nowhere Dense Classes of Graphs
- Bidimensionality and Geometric Graphs
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Monadic datalog and the expressive power of languages for Web information extraction
- Fast Counting with Bounded Treewidth
- Generalized finite automata theory with an application to a decision problem of second-order logic
- The number of labeled k-dimensional trees
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph-Theoretic Concepts in Computer Science
- Algorithms and Data Structures
- Finding Branch-Decompositions and Rank-Decompositions
- Computations by fly-automata beyond monadic second-order logic
- 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
- 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
- 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: Practical algorithms for MSO model-checking on tree-decomposable graphs
