The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

DOI10.1016/0890-5401(90)90043-HzbMath0722.03008OpenAlexW2028357390MaRDI QIDQ2641288

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(90)90043-h

zbMATH Keywords

decidability recognition definability formal languages universal algebra context-free set many-sorted algebra of graphs monadic second-order logic of graphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Applications of universal algebra in computer science (08A70) Structural characterization of families of graphs (05C75) Decidability of theories and sets of sentences (03B25)

Related Items

Monadic second-order definable graph transductions: a survey, Node replacements in embedding normal form., The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions., A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, The complexity of connectivity problems on context-free graph languages, 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 recurrence template for several parameters in series-parallel graphs, The nonexistence of reduction rules giving an embedding into a $k$-tree, Regularity and locality in $k$-terminal graphs, Context-free graph languages of bounded degree are generated by apex graph grammars, The complexity of induced minors and related problems, Notes on complexity of packing coloring, Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, On the complexity of rainbow coloring problems, Monadic second-order definable text languages, The monadic second-order logic of graphs. X: Linear orderings, Arity and alternation in second-order logic, The obstructions of a minor-closed set of graphs defined by a context-free grammar, Pushdown reachability with constant treewidth, On interval routing schemes and treewidth, Logical description of context-free graph languages, Structure and algorithms for (cap, even hole)-free graphs, Reconfiguration in bounded bandwidth and tree-depth, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Tree-width and the monadic quantifier hierarchy., Spanners of bounded degree graphs, Splitting a graph into disjoint induced paths or cycles., An FPT 2-approximation for tree-cut decomposition, Automata for the verification of monadic second-order graph properties, The P3 infection time is W[1-hard parameterized by the treewidth], Path-contractions, edge deletions and connectivity preservation, The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Upper bounds to the clique width of graphs, On the tree-width of even-hole-free graphs, Explicit linear kernels for packing problems, Counting linear extensions: parameterizations by treewidth, On the planar split thickness of graphs, Crossing number for graphs with bounded pathwidth, Canonical representations of partial 2- and 3-trees, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, A branch-and-price-and-cut method for computing an optimal bramble, Subexponential fixed-parameter algorithms for partial vector domination, A linear time algorithm for the $3$-neighbour travelling salesman problem on a Halin graph and extensions, On distance-preserving elimination orderings in graphs: complexity and algorithms, On compatibility and incompatibility of collections of unrooted phylogenetic trees, Fly-automata for checking $\mathrm{MSO}_2$ graph properties, Context-free hypergraph grammars have the same term-generating power as attribute grammars, The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs, Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications, Algorithmic meta-theorems for restrictions of treewidth, Parameterized modal satisfiability, Towards fixed-parameter tractable algorithms for abstract argumentation, Practical access to dynamic programming on tree decompositions, On the approximate compressibility of connected vertex cover, Complexity of path-forming games, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Querying linguistic treebanks with monadic second-order logic in linear time, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, The complexity of frugal colouring, On the (parameterized) complexity of recognizing well-covered ($r$,$\ell$)-graph, Parameterized algorithms for conflict-free colorings of graphs, Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization, Cluster deletion on interval graphs and split related graphs, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Approximation in (Poly-) logarithmic space, Reducing graph transversals via edge contractions, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Algorithmic aspects of secure connected domination in graphs, Algorithmic aspects of 2-secure domination in graphs, A unifying model for locally constrained spanning tree problems, Computing with graph rewriting systems with priorities, Hitting forbidden induced subgraphs on bounded treewidth graphs, Algorithmic aspects of Roman domination in graphs, Parameterized complexity of vertex colouring, A comparison of compatible, finite, and inductive graph properties, A relaxation of the directed disjoint paths problem: a global congestion metric helps, Faster algorithms for quantitative verification in bounded treewidth graphs, Upper bounds on the size of obstructions and intertwines, A partial k-arboretum of graphs with bounded treewidth, Nondeterministic operations on finite relational structures, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, On computing graph minor obstruction sets, On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem, A comparison of tree transductions defined by monadic second order logic and by attribute grammars, The monadic second-order logic of graphs. VIII: Orientations, Optimal centrality computations within bounded clique-width graphs, Maximum matching in almost linear time on graphs of bounded clique-width, Colouring non-even digraphs, A meta-theorem for distributed certification, Uniform and nonuniform recognizability., Counting modulo quantifiers on finite structures, Reduction algorithms for graphs of small treewidth, On hyperedge replacement and BNLC graph grammars, FPT algorithms for generalized feedback vertex set problems, An FPT algorithm for matching cut and d-cut, Verifying graph programs with monadic second-order logic, On the impact of treewidth in the computational complexity of freezing dynamics, New limits of treewidth-based tractability in optimization, An algorithmic metatheorem for directed treewidth, Compatibility of unrooted phylogenetic trees is FPT, Trees, grids, and MSO decidability: from graphs to matroids, On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity, Compactors for parameterized counting problems, A linear time algorithm for metric dimension of cactus block graphs, Algorithmic aspects of total Roman and total double Roman domination in graphs, Computing the zig-zag number of directed graphs, Contraction bidimensionality of geometric intersection graphs, Structural parameterizations for boxicity, (Total) vector domination for graphs with bounded branchwidth, On the feedback vertex set polytope of a series-parallel graph, Between treewidth and clique-width, Reduction rules for the maximum parsimony distance on phylogenetic trees, On (uniform) hierarchical decompositions of finite structures and model-theoretic geometry, An asymptotic analysis of labeled and unlabeled $k$-trees, Recognizability equals definability for graphs of bounded treewidth and bounded chordality, Planar disjoint-paths completion, Parameterized algorithms for non-separating trees and branchings in digraphs, The VC-dimension of graphs with respect to $k$-connected subgraphs, Vertex-minors, monadic second-order logic, and a conjecture by Seese, Kernelization using structural parameters on sparse graph classes, The parameterised complexity of list problems on graphs of bounded treewidth, Characterizing width two for variants of treewidth, Algorithmic aspects of open neighborhood location-domination in graphs, XML schema, tree logic and sheaves automata, Algorithmic uses of the Feferman-Vaught theorem, Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms, Increasing the minimum degree of a graph by contractions, Preprocessing subgraph and minor problems: when does a small vertex cover help?, Kernel bounds for path and cycle problems, Lower bounds on the complexity of $\mathsf{MSO}_1$ model-checking, Optimization problems in dotted interval graphs, Courcelle's theorem -- a game-theoretic approach, Are there any good digraph width measures?, Meta-kernelization with structural parameters, Sublinear separators, fragility and subexponential expansion, Complexity of total outer-connected domination problem in graphs, Directed elimination games, The complexity of two graph orientation problems, On low tree-depth decompositions, Injective colorings with arithmetic constraints, Tree-width of hypergraphs and surface duality, Model-checking hierarchical structures, Distance three labelings of trees, On graph contractions and induced minors, On the model-checking of monadic second-order formulas with edge set quantifications, Decomposition width of matroids, On the complexity of some colorful problems parameterized by treewidth, A combinatorial optimization algorithm for solving the branchwidth problem, Contracting planar graphs to contractions of triangulations, Quadratic kernelization for convex recoloring of trees, The dag-width of directed graphs, Computing role assignments of proper interval graphs in polynomial time, On rules with existential variables: walking the decidability line, On the algorithmic effectiveness of digraph decompositions and complexity measures, Parameterizing cut sets in a graph by the number of their components, Confronting intractability via parameters, Cycle-maximal triangle-free graphs, Practical algorithms for MSO model-checking on tree-decomposable graphs, Spanners in sparse graphs, Approximation algorithms for intersection graphs, The string generating power of context-free hypergraph grammars, The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability, A regular characterization of graph languages definable in monadic second-order logic, Complexity of conflict-free colorings of graphs, A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs, Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques, Efficient algorithms for the \textsc{max~$k$-vertex cover problem}, Algorithms for decision problems in argument systems under preferred semantics, Tree $t$-spanners in outerplanar graphs via supply demand partition, Basic notions of universal algebra for language theory and graph grammars, The monadic second-order logic of graphs. IX: Machines and their behaviours, Characterization and complexity of uniformly nonprimitive labeled 2-structures, The monadic second-order logic of graphs. VII: Graphs as relational structures, On first-order definitions of subgraph isomorphism properties, On the path-width of integer linear programming, Monadic second-order evaluations on tree-decomposable graphs, Recursively indefinite databases, Efficient computation of the characteristic polynomial of a tree and related tasks, Partitioning graphs of supply and demand, On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width, Complexity of secure sets, Fast compatibility testing for rooted phylogenetic trees, The complexity ecology of parameters: An illustration using bounded max leaf number, Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width, Complexity of conditional colorability of graphs, Treewidth and logical definability of graph products, A single-exponential FPT algorithm for the $K_4$-\textsc{minor cover} problem, On the treewidth of dynamic graphs, Juggrnaut: using graph grammars for abstracting unbounded heap structures, Recursive queries and context-free graph grammars, Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction, The parameterized complexity of the induced matching problem, Computational properties of argument systems satisfying graph-theoretic constraints, Induced packing of odd cycles in planar graphs, On bounded-degree vertex deletion parameterized by treewidth, Parameterized leaf power recognition via embedding into graph products, The monadic second-order logic of graphs. IV: Definability properties of equational graphs, Algorithms and almost tight results for 3-colorability of small diameter graphs, Complexity issues of perfect secure domination in graphs, Iterated Type Partitions, Increasing the Minimum Degree of a Graph by Contractions, Second-Order Finite Automata, A Retrospective on (Meta) Kernelization, Efficient Problem Solving on Tree Decompositions Using Binary Decision Diagrams, Provenance Circuits for Trees and Treelike Instances, A New Approach for Contact Graph Representations and Its Applications, Kernelization of Cycle Packing with Relaxed Disjointness Constraints, Unnamed Item, Ensuring Correctness of Model Transformations While Remaining Decidable, Fixed-Parameter Tractability of Treewidth and Pathwidth, A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata, Unnamed Item, Graph decompositions and tree automata in reasoning with uncertainty, The monadic second-order logic of graphs, II: Infinite graphs of bounded width, On the Satisfiability of Quantum Circuits of Small Treewidth, Transforming graph states using single-qubit operations, Subexponential Fixed-Parameter Algorithms for Partial Vector Domination, Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth, Recognizability equals definability for partial k-paths, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, A geometrical view of the determinization and minimization of finite-state automata, Graph Bisection with Pareto Optimization, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, Between Treewidth and Clique-Width, Quantified Conjunctive Queries on Partially Ordered Sets, Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size, Finite Integer Index of Pathwidth and Treewidth, Recognizable languages of arrows and cospans, Logics of Finite Hankel Rank, Unique key Horn functions, Bounded Treewidth and Space-Efficient Linear Algebra, On the computational complexity of the bipartizing matching problem, Distance Constrained Labelings of Trees, Large Induced Subgraphs via Triangulations and CMSO, Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs, Convex Independence in Permutation Graphs, Parameterized complexity of computing maximum minimal blocking and hitting sets, Computing partial hypergraphs of bounded width, Unnamed Item, Unnamed Item, Unnamed Item, Obstructions for matroids of path-width at most $k$ and graphs of linear rank-width at most $k$, Grid induced minor theorem for graphs of small degree, Fixed parameterized algorithms for generalized feedback vertex set problems, Unnamed Item, Unnamed Item, Navigational and Rule-Based Languages for Graph Databases, Parameterized and Exact Algorithms for Class Domination Coloring, On Structural Parameterizations of Graph Motif and Chromatic Number, On algorithmic applications of sim-width and mim-width of $(H_1,H_2)$-free graphs, Fair allocation of indivisible items with conflict graphs, Unnamed Item, On Guarding Orthogonal Polygons with Sliding Cameras, Equivalent definitions of recognizability for sets of graphs of bounded tree-width, Beyond Outerplanarity, Unnamed Item, Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity, The size of an intertwine, Computing Role Assignments of Proper Interval Graphs in Polynomial Time, Reducing CMSO model checking to highly connected graphs, Parameterized Leaf Power Recognition via Embedding into Graph Products, Fifty years of the spectrum problem: survey and new results, Practical Access to Dynamic Programming on Tree Decompositions, Yes, the “missing axiom” of matroid theory is lost forever, Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory, Parallel algorithms with optimal speedup for bounded treewidth, 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, The definition in monadic second-order logic of modular decompositions of ordered graphs, Unnamed Item, The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey, First order properties on nowhere dense structures, Hitting Forbidden Minors: Approximation and Kernelization, Are There Any Good Digraph Width Measures?, A $c^k n$ 5-Approximation Algorithm for Treewidth, Complexity of Roman {2}-domination and the double Roman domination in graphs, Towards a characterization of order-invariant queries over tame graphs, Unnamed Item, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Enumeration of Minimal Dominating Sets and Variants, Bidimensionality and Kernels, Causality in Bounded Petri Nets is MSO Definable, Parameterized Complexity Results for 1-safe Petri Nets, Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs, Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques, Parameterized Complexity of Discrete Morse Theory, A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata, Integrating and Sampling Cuts in Bounded Treewidth Graphs, Finding good tree decompositions by local search, Dynamic algorithms for graphs of bounded treewidth, Kernelization: New Upper and Lower Bound Techniques, Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs, Euler Digraphs, Unnamed Item, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Unnamed Item, Graph decompositions for cartesian products, Algorithmic aspects of total Roman {3}-domination in graphs, Uncountably many minimal hereditary classes of graphs of unbounded clique-width, On the data complexity of consistent query answering over graph databases, Star colouring of bounded degree graphs and regular graphs, Handle-rewriting hypergraph grammars, Adapting the directed grid theorem into an \textsf{FPT} algorithm, A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem, Tree-edges deletion problems with bounded diameter obstruction sets, The $d$-precoloring problem for $k$-degenerate graphs, Some notes on bounded starwidth graphs, Hyperfinite MV-algebras, Quantified conjunctive queries on partially ordered sets, Tree automata and pigeonhole classes of matroids. I, Finding all leftmost separators of size $\le k$, A general framework for path convexities, Second-order finite automata, Structural parameterization for minimum conflict-free colouring, Vertex partitioning problems on graphs with bounded tree width, The complexity of restricted star colouring, Space-efficient vertex separators for treewidth, Eccentricity queries and beyond using hub labels, Boundary classes for graph problems involving non-local properties, Distance from triviality 2.0: hybrid parameterizations, Regular queries on graph databases, Parameterized and exact algorithms for class domination coloring, On orthogonally guarding orthogonal polygons with bounded treewidth, Definability equals recognizability for $k$-outerplanar graphs and $l$-chordal partial $k$-trees, Colorful edge decomposition of graphs: some polynomial cases, The $k$-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing, Bisection of bounded treewidth graphs by convolutions, Sparse obstructions for minor-covering parameters, The tree-width of C, Dichotomies properties on computational complexity of $S$-packing coloring problems, Hitting forbidden subgraphs in graphs of bounded treewidth, Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity, An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion, A polynomial kernel for block graph deletion, Complexity aspects of variants of independent Roman domination in graphs, On the vertex cover $P_3$ problem parameterized by treewidth, Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory, On the satisfiability of quantum circuits of small treewidth, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, An approval-based model for single-step liquid democracy, 1-perfectly orientable $K_4$-minor-free and outerplanar graphs, Parameterized edge Hamiltonicity, Characterizing graphs of maximum matching width at most 2, FPT algorithms to compute the elimination distance to bipartite graphs and more, Specifying graph languages with type graphs, Recognizable series on graphs and hypergraphs, Logics for unordered trees with data constraints, Grad and classes with bounded expansion. I: Decompositions, Grad and classes with bounded expansion. II: Algorithmic aspects, Maximizing the strong triadic closure in split graphs and proper interval graphs, Local search is a PTAS for feedback vertex set in minor-free graphs, Fixpoint logics over hierarchical structures, On nowhere dense graphs, Bundled crossings revisited, Homotopy height, grid-major height and graph-drawing height, Graph theory in Coq: minors, treewidth, and isomorphisms, Coloring graphs without short cycles and long induced paths, Contracting graphs to paths and trees, Digraphs of bounded elimination width, Branch decomposition heuristics for linear matroids, Syntactic recognizability of graphs with fuzzy attributes, On structural parameterizations of the bounded-degree vertex deletion problem, Branch-depth: generalizing tree-depth of graphs, On the complexity of dominating set problems related to the minimum all-ones problem, Algorithms for finding distance-edge-colorings of graphs, An improvement of Reed's treewidth approximation, Waypoint routing on bounded treewidth graphs, Entailment is undecidable for symbolic heap separation logic formulæ with non-established inductive rules, Coloring temporal graphs, Detecting fixed patterns in chordal graphs in polynomial time, Tree decomposition and discrete optimization problems: a survey, An extended tree-width notion for directed graphs related to the computation of permanents, On the complexity of the identifiable subgraph problem, The computational complexity of the parallel knock-out problem, Algebraic recognizability of regular tree languages, Branch-width, parse trees, and monadic second-order logic for matroids., Recognizability of graph and pattern languages, Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms, Minimum $k$-path vertex cover, Message-passing automata are expressively equivalent to EMSO logic, Treewidth, crushing and hyperbolic volume, Partitioning graphs into induced subgraphs, Whither semantics?, The role of planarity in connectivity problems parameterized by treewidth, Nontrivial path covers of graphs: existence, minimization and maximization, Hitting minors on bounded treewidth graphs. III. Lower bounds, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms, On the width of regular classes of finite structures, Convex dominating sets in maximal outerplanar graphs, Computing the number of $k$-component spanning forests of a graph with bounded treewidth, Efficient parallel algorithms for parameterized problems, Cooperative games with overlapping coalitions: charting the tractability frontier, Evaluating Datalog via tree automata and cycluits, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?, The recognizability of sets of graphs is a robust property, Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, On the parameterized complexity of the acyclic matching problem, Problems hard for treewidth but easy for stable gonality, On the minimum cycle cover problem on graphs with bounded co-degeneracy, Grouped domination parameterized by vertex cover, twin cover, and beyond, On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves, Clique‐width: Harnessing the power of atoms, The firebreak problem, Edge-treewidth: algorithmic and combinatorial properties, Structural parameterization of cluster deletion, Monoidal Width, (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth, First-order Logic with Connectivity Operators, Linear‐time algorithms for eliminating claws in graphs, Tangle bases: Revisited, Optimizing concurrency under Scheduling by Edge Reversal, Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width, Reducing the vertex cover number via edge contractions, Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks, Grouped domination parameterized by vertex cover, twin cover, and beyond, Target set selection with maximum activation time, Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, Complexity aspects of restrained Roman domination in graphs, Deletion to scattered graph classes. I: Case of finite number of graph classes, Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes, Treewidth versus clique number. II: Tree-independence number, Hardness transitions and uniqueness of acyclic colouring, Monoidal Width: Capturing Rank Width, Tree automata and pigeonhole classes of matroids. II, Recognizing map graphs of bounded treewidth, Cosecure domination: hardness results and algorithms, Exponential time analysis of confluent and boundary eNCE graph languages, Bounded tree-width and LOGCFL, On reduction algorithms for graphs with small treewidth, Reduction algorithms for constructing solutions in graphs with small treewidth, Implicit representation of relations, Extended MSO model checking via small vertex integrity, Some new algorithmic results on co-secure domination in graphs, Three remarks on $\mathbf{W}_{\mathbf{2}}$ graphs, On $d$-stable locally checkable problems parameterized by mim-width, Unnamed Item, Unnamed Item, Algorithmic aspects of certified domination in graphs, Algorithmic aspects of total Roman ${2}$-domination in graphs, Algorithmic Aspects of Quasi-Total Roman Domination in Graphs, A meta-theorem for distributed certification, Program Verification with Separation Logic, On Monotonic Determinacy and Rewritability for Recursive Queries and Views, Feature automata and recognizable sets of feature trees, An Improvement of Reed’s Treewidth Approximation, A parallel algorithm for edge-coloring partial k-trees, Generalized rational relations and their logical definability, Parametric problems on graphs of bounded tree-width, Regular-factors in the complements of partial k-trees, Practical algorithms on partial k-trees with an application to domination-like problems, A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, On spectra of sentences of monadic second order logic with counting, A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs, Identifying Codes in Line Graphs, Properties of Large 2-Crossing-Critical Graphs, Unnamed Item, Unnamed Item, Decomposability helps for deciding logics of knowledge and belief, Recognizable sets of graphs of bounded tree-width, Grundy Distinguishes Treewidth from Pathwidth, Decision problems for edge grammars, MSO definable text languages, Adapting the Directed Grid Theorem into an FPT Algorithm, Algorithmic aspects of outer independent Roman domination in graphs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs, Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds, Minimum size tree-decompositions, Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth, Bundled Crossings Revisited, First-Order Model-Checking in Random Graphs and Complex Networks, Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes, Minimum size tree-decompositions, Unnamed Item, Independent roman $\{3\}$-domination, A Practical Approach to Courcelle's Theorem, To Approximate Treewidth, Use Treelength!, Unnamed Item, Grid structures and undecidable constraint theories, Clique-perfectness of complements of line graphs, A linear‐time algorithm for broadcast domination in a tree, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The edge-disjoint paths problem is NP-complete for series-parallel graphs, Unnamed Item, Unnamed Item, Finding cut-vertices in the square roots of a graph, Recognizing hyperelliptic graphs in polynomial time, On low rank-width colorings, Computing LOGCFL certificates, A Greibach normal form for context-free graph grammars, Two strikes against perfect phylogeny, Constructing tree decompositions of graphs with bounded gonality, The Parameterized Complexity of Graph Cyclability, Complexity of fall coloring for restricted graph classes, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Clique-width of point configurations, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On the (di)graphs with (directed) proper connection number two, Unnamed Item, Inserting one edge into a simple drawing is hard, Minimum eccentricity shortest path problem with respect to structural parameters, Non-preemptive tree packing, The descriptive complexity of subgraph isomorphism without numerics, Relating Structure and Power: Comonadic Semantics for Computational Resources, Clique-perfectness of complements of line graphs, Unnamed Item, On the tractability of covering a graph with 2-clubs, Elimination Distance to Bounded Degree on Planar Graphs, An Experimental Study of the Treewidth of Real-World Graph Data, Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs, Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth., Uniformly Automatic Classes of Finite Structures, Treewidth of display graphs: bounds, brambles and applications, On the treewidth of random geometric graphs and percolated grids, Unnamed Item, Unnamed Item, Unnamed Item, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs, Contraction-Bidimensionality of Geometric Intersection Graphs, A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES, Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs, Unnamed Item, Unnamed Item, Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming, Algorithmic complexity of weakly connected Roman domination in graphs, On Treewidth and Related Parameters of Random Geometric Graphs

Cites Work