The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 4081531
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
Cites work
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Characterization and Recognition of Partial 3-Trees
- Complexity of Finding Embeddings in a k-Tree
- Easy problems for tree-decomposable graphs
- Forbidden minors characterization of partial 3-trees
- Graph expressions and graph rewritings
- Graph minors. IV: Tree-width and well-quasi-ordering
- Graph minors. V. Excluding a planar graph
- Graph minors. XIII: The disjoint paths problem
- scientific article; zbMATH DE number 3885965 (Why is no real title available?)
- scientific article; zbMATH DE number 4049099 (Why is no real title available?)
- scientific article; zbMATH DE number 4060712 (Why is no real title available?)
- scientific article; zbMATH DE number 4060748 (Why is no real title available?)
- scientific article; zbMATH DE number 4062614 (Why is no real title available?)
- scientific article; zbMATH DE number 176761 (Why is no real title available?)
- scientific article; zbMATH DE number 177426 (Why is no real title available?)
- scientific article; zbMATH DE number 177465 (Why is no real title available?)
- scientific article; zbMATH DE number 3517129 (Why is no real title available?)
- scientific article; zbMATH DE number 1142299 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 219268 (Why is no real title available?)
- Infinite hypergraphs. I: Basic properties
- Monadic second-order evaluations on tree-decomposable graphs
- On Some Variants of the Bandwidth Minimization Problem
- Steiner trees, partial 2–trees, and minimum IFI networks
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The monadic second-order logic of graphs. IV: Definability properties of equational graphs
- The structure of the models of decidable monadic theories of graphs
- Über eine Eigenschaft der ebenen Komplexe
Cited in
(only showing first 100 items - show all)- Treewidth and logical definability of graph products
- From a zoo to a zoology: Towards a general theory of graph polynomials
- Computational properties of argument systems satisfying graph-theoretic constraints
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- A partial k-arboretum of graphs with bounded treewidth
- Monadic second-order definable graph transductions: a survey
- Improved self-reduction algorithms for graphs with bounded treewidth
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- The obstructions of a minor-closed set of graphs defined by a context-free grammar
- Tree-width and the monadic quantifier hierarchy.
- Counting \(H-\)colorings of partial \(k-\)trees
- Listing all potential maximal cliques of a graph
- Safe sets in graphs: graph classes and structural parameters
- Combinatorial problems on \(H\)-graphs
- Finding a potential community in networks
- Parameterized complexity of the spanning tree congestion problem
- Querying linguistic treebanks with monadic second-order logic in linear time
- Infinite hypergraphs. I: Basic properties
- Chordal bipartite graphs of bounded tree- and clique-width
- The monadic second-order logic of graphs. VIII: Orientations
- Spanners of bounded degree graphs
- Automata for the verification of monadic second-order graph properties
- The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
- Upper bounds to the clique width of graphs
- Parameterized complexity of \((A,\ell)\)-path packing
- Vertex partitioning problems on graphs with bounded tree width
- On caterpillar factors in graphs
- Modifying a graph using vertex elimination
- Partitioning a graph into disjoint cliques and a triangle-free graph
- Handle-rewriting hypergraph grammars
- Degree-constrained decompositions of graphs: Bounded treewidth and planarity
- On some domination colorings of graphs
- A linear kernel for finding square roots of almost planar graphs
- Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
- Computing square roots of graphs with low maximum degree
- Complexity and algorithms for recognizing polar and monopolar graphs
- Branch-width, parse trees, and monadic second-order logic for matroids.
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Completely independent spanning trees in (partial) \(k\)-trees
- The relative clique-width of a graph
- Parameterized and exact algorithms for class domination coloring
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- Finding cactus roots in polynomial time
- \((1, j)\)-set problem in graphs
- Large Induced Subgraphs via Triangulations and CMSO
- Safe sets in graphs: graph classes and structural parameters
- Parameterized and exact algorithms for class domination coloring
- Complexity results for the spanning tree congestion problem
- Parameterized algorithms for non-separating trees and branchings in digraphs
- Graph decompositions for cartesian products
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width
- scientific article; zbMATH DE number 4081531 (Why is no real title available?)
- scientific article; zbMATH DE number 177454 (Why is no real title available?)
- The complexity of two graph orientation problems
- scientific article; zbMATH DE number 475615 (Why is no real title available?)
- Automata-based Representations for Infinite Graphs
- scientific article; zbMATH DE number 1543064 (Why is no real title available?)
- Recognizability equals definability for partial k-paths
- Combinatorial and computational aspects of graph packing and graph decomposition
- The obstructions of a minor-closed set of graphs defined by hyperedge replacement can be constructed
- A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths
- Confronting intractability via parameters
- scientific article; zbMATH DE number 219229 (Why is no real title available?)
- scientific article; zbMATH DE number 809155 (Why is no real title available?)
- Reducing CMSO model checking to highly connected graphs
- Parameterized Complexity of $$(A,\ell )$$-Path Packing
- A Survey on Spanning Tree Congestion
- A Retrospective on (Meta) Kernelization
- Recognizable sets of graphs of bounded tree-width
- Parameterized complexity of safe set
- scientific article; zbMATH DE number 7310159 (Why is no real title available?)
- Guarded second-order logic, spanning trees, and network flows
- A linear‐time algorithm for broadcast domination in a tree
- Treewidth in non-ground answer set solving and alliance problems in graphs
- MSOL restricted contractibility to planar graphs
- On the complexity of finding a potential community
- Complexity of the Packing Coloring Problem for Trees
- The monadic second-order logic of graphs XVI : Canonical graph decompositions
- Computer Science Logic
- Monadic second-order model-checking on decomposable matroids
- Complexity and approximation of the constrained forest problem
- An algorithmic meta-theorem for graph modification to planarity and FOL
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
- Exploring the gap between treedepth and vertex cover through vertex integrity
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Monoidal Width
- On structural parameterizations of star coloring
- Extended MSO model checking via small vertex integrity
- Spanners in sparse graphs
- How I got to like graph polynomials
- Twin-treewidth: a single-exponential logic-based approach
- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- Characterization and complexity of uniformly nonprimitive labeled 2-structures
- Thick forests
- Monadic second-order evaluations on tree-decomposable graphs
- Decremental sensitivity oracles for covering and packing minors
- On the parameterized complexity of odd coloring
- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- An algorithmic meta-theorem for graph modification to planarity and FOL
This page was built for publication: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4012672)
