The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues

DOI10.1051/ITA/1992260302571zbMath0754.03006OpenAlexW182050876MaRDI QIDQ4012672

No author found.

Publication date: 27 September 1992

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92418

zbMATH Keywords

monadic second-order logicgraphshypergraphsminorsformal languagequadratic algorithmstree-decompositions

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42)

Related Items (88)

Monadic second-order definable graph transductions: a survey ⋮ On the Complexity of Finding a Potential Community ⋮ Parameterized Complexity of $$(A,\ell )$$-Path Packing ⋮ Handle-rewriting hypergraph grammars ⋮ A Survey on Spanning Tree Congestion ⋮ A Retrospective on (Meta) Kernelization ⋮ 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 ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ Degree-constrained decompositions of graphs: Bounded treewidth and planarity ⋮ \((1, j)\)-set problem in graphs ⋮ Safe sets in graphs: graph classes and structural parameters ⋮ Complexity of the Packing Coloring Problem for Trees ⋮ The relative clique-width of a graph ⋮ Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ A general framework for path convexities ⋮ The monadic second-order logic of graphs, II: Infinite graphs of bounded width ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ On some domination colorings of graphs ⋮ A linear kernel for finding square roots of almost planar graphs ⋮ Parameterized and exact algorithms for class domination coloring ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ Recognizability equals definability for partial k-paths ⋮ The obstructions of a minor-closed set of graphs defined by a context-free grammar ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Computing square roots of graphs with low maximum degree ⋮ Recognizable sets of graphs of bounded tree-width ⋮ Monoidal Width ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Combinatorial problems on \(H\)-graphs ⋮ The complexity of two graph orientation problems ⋮ Safe Sets in Graphs: Graph Classes and Structural Parameters ⋮ On structural parameterizations of star coloring ⋮ Unnamed Item ⋮ Spanners of bounded degree graphs ⋮ Extended MSO model checking via small vertex integrity ⋮ Automata-based Representations for Infinite Graphs ⋮ Automata for the verification of monadic second-order graph properties ⋮ Parameterized Complexity of Safe Set ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Complexity and algorithms for recognizing polar and monopolar graphs ⋮ On caterpillar factors in graphs ⋮ Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ Confronting intractability via parameters ⋮ Spanners in sparse graphs ⋮ The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability ⋮ Upper bounds to the clique width of graphs ⋮ Reducing CMSO model checking to highly connected graphs ⋮ Finding a potential community in networks ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ 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 ⋮ MSOL restricted contractibility to planar graphs ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ Tree-width of graphs without a \(3\times 3\) grid minor ⋮ Complexity of the packing coloring problem for trees ⋮ Monadic second-order model-checking on decomposable matroids ⋮ Complexity and approximation of the constrained forest problem ⋮ Satisfactory graph partition, variants, and generalizations ⋮ Querying linguistic treebanks with monadic second-order logic in linear time ⋮ A linear‐time algorithm for broadcast domination in a tree ⋮ Complexity Results for the Spanning Tree Congestion Problem ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Finding cactus roots in polynomial time ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ Completely independent spanning trees in (partial) \(k\)-trees ⋮ Treewidth and logical definability of graph products ⋮ Unnamed Item ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Algorithms for unipolar and generalized split graphs ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ From a zoo to a zoology: Towards a general theory of graph polynomials ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ Finding Cactus Roots in Polynomial Time ⋮ Infinite hypergraphs. I: Basic properties ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Computational properties of argument systems satisfying graph-theoretic constraints ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ Unnamed Item ⋮ The monadic second-order logic of graphs. VIII: Orientations ⋮ Modifying a graph using vertex elimination ⋮ Graph decompositions for cartesian products ⋮ Counting \(H-\)colorings of partial \(k-\)trees ⋮ Listing all potential maximal cliques of a graph ⋮ Partitioning a graph into disjoint cliques and a triangle-free graph ⋮ Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

• Monadic second-order evaluations on tree-decomposable 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
• Forbidden minors characterization of partial 3-trees
• Graph minors. V. Excluding a planar graph
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Infinite hypergraphs. I: Basic properties
• Graph minors. XIII: The disjoint paths problem
• Graph minors. IV: Tree-width and well-quasi-ordering
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Über eine Eigenschaft der ebenen Komplexe
• Steiner trees, partial 2–trees, and minimum IFI networks
• On Some Variants of the Bandwidth Minimization Problem
• Easy problems for tree-decomposable graphs
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Characterization and Recognition of Partial 3-Trees
• Complexity of Finding Embeddings in a k-Tree
• Graph expressions and graph rewritings
• 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: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues