Monadic second-order evaluations on tree-decomposable graphs
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 219229
- Easy problems for tree-decomposable graphs
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- scientific article; zbMATH DE number 4081531
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
Cites work
- Attribute grammars. Definitions, systems and bibliography
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Characterization and Recognition of Partial 3-Trees
- Complexity of Finding Embeddings in a k-Tree
- Complexity of path-forming games
- Easy problems for tree-decomposable graphs
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Graph expressions and graph rewritings
- scientific article; zbMATH DE number 4095510 (Why is no real title available?)
- scientific article; zbMATH DE number 177426 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 4121424 (Why is no real title available?)
- Hyperedge replacement: grammars and languages
- Linear-time computability of combinatorial problems on series-parallel graphs
- Linear-time computation of optimal subgraphs of decomposable graphs
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- The NP-completeness column: an ongoing guide
- The Recognition of Series Parallel Digraphs
Cited in
(99)- Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
- On the OBDD size for graphs of bounded tree- and clique-width
- The NLC-width and clique-width for powers of graphs of bounded tree-width
- Decidability of the finiteness of ranges of tree transductions
- All structured programs have small tree width and good register allocation
- A partial k-arboretum of graphs with bounded treewidth
- Nondeterministic operations on finite relational structures
- Partial and perfect path covers of cographs
- Monadic second-order definable graph transductions: a survey
- Finite tree automata with cost functions
- Probabilistic hyperedge replacement grammars
- Logical description of context-free graph languages
- Tree-width and the monadic quantifier hierarchy.
- Query efficient implementation of graphs of bounded clique-width
- The monadic second-order logic of graphs. XII: Planar graphs and planar maps
- A comparison of tree transductions defined by monadic second order logic and by attribute grammars
- The evaluation of first-order substitution is monadic second-order compatible
- Listing all potential maximal cliques of a graph
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Querying linguistic treebanks with monadic second-order logic in linear time
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- A comparison of compatible, finite, and inductive graph properties
- The monadic second-order logic of graphs. VIII: Orientations
- The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
- Upper bounds to the clique width of graphs
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Galois connections for patterns: an algebra of labelled graphs
- On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
- Maximum matching in almost linear time on graphs of bounded clique-width
- Evaluation diversity for graph conditions
- A new approach on locally checkable problems
- Waypoint routing on bounded treewidth graphs
- Frameworks for designing in-place graph algorithms
- Bounded treewidth as a key to tractability of knowledge representation and reasoning
- Structural tractability of enumerating CSP solutions
- Algorithms for finding distance-edge-colorings of graphs
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Tree decomposition and discrete optimization problems: a survey
- Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
- Linear layouts measuring neighbourhoods in graphs
- On the computational complexity of the bipartizing matching problem
- Hitting forbidden minors: approximation and kernelization
- On the tree-width of planar graphs
- Fixed-parameter tractability of treewidth and pathwidth
- Large Induced Subgraphs via Triangulations and CMSO
- Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
- Planar disjoint-paths completion
- Extension complexity, MSO logic, and treewidth
- Courcelle's theorem for triangulations
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- The Clique-Width of Tree-Power and Leaf-Power Graphs
- Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
- Kernel bounds for path and cycle problems
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- scientific article; zbMATH DE number 177454 (Why is no real title available?)
- Courcelle's theorem -- a game-theoretic approach
- Dynamic algorithms for graphs of bounded treewidth
- Least solutions of equations over \(\mathcal{N}\)
- Confronting intractability via parameters
- scientific article; zbMATH DE number 219229 (Why is no real title available?)
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- scientific article; zbMATH DE number 809155 (Why is no real title available?)
- Algorithms for decision problems in argument systems under preferred semantics
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- Data-compression for parametrized counting problems on sparse graphs
- Parameterized complexity of fair vertex evaluation problems
- Algebras for tree decomposable graphs
- \(k\)-best solutions of MSO problems on tree-decomposable graphs
- An improved fixed-parameter algorithm for one-page crossing minimization
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- A Practical Approach to Courcelle's Theorem
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- Inductive computations on graphs defined by clique-width expressions
- Tree decompositions and social graphs
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Computations by fly-automata beyond monadic second-order logic
- Algorithmic uses of the Feferman-Vaught theorem
- Treelength of series-parallel graphs
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- Dominator coloring and CD coloring in almost cluster graphs
- Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs
- Basic notions of universal algebra for language theory and graph grammars
- A simple linear-time algorithm for finding path-decompositions of small width
- t-linear coloring in graphs with given small lenient-tree-width
- Meta-theorems for graph polynomials
- Solution discovery via reconfiguration for problems in P
- Solving a family of multivariate optimization and decision problems on classes of bounded expansion
- Model checking disjoint-paths logic on topological-minor-free graph classes
- Dominator coloring and CD coloring in almost cluster graphs
- Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings
- Courcelle's theorem for Lipschitz continuity
- Bridging treewidth and clique-width via cograph-modular-treewidth
- On the rank and the general position number in cycle convexity
- Safe separators for treewidth
- Trees, grids, and MSO decidability: from graphs to matroids
- A local characterization of bounded clique-width for line graphs
- Partitioning graphs of supply and demand
This page was built for publication: Monadic second-order evaluations on tree-decomposable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685464)
