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

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

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 logic graphs hypergraphs minors formal language quadratic algorithms tree-decompositions

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

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

This page was built for publication: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues