Easy problems for tree-decomposable graphs

Recommendations

scientific article; zbMATH DE number 4081531
On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
scientific article; zbMATH DE number 4060712
Practical algorithms for MSO model-checking on tree-decomposable graphs
A Practical Approach to Courcelle's Theorem

Cited in

(only showing first 100 items - show all)

Approximability of partitioning graphs with supply and demand
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
Computational properties of argument systems satisfying graph-theoretic constraints
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
Algorithms for recognition of regular properties and decomposition of recursive graph families
The monadic second-order logic of graphs. VII: Graphs as relational structures
Complexity of path-forming games
All structured programs have small tree width and good register allocation
Upper bounds on the size of obstructions and intertwines
Characterizing multiterminal flow networks and computing flows in networks of small treewidth
On the pathwidth of chordal graphs
NP-completeness of minimum spanner problems
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
\(k\)-NLC graphs and polynomial algorithms
Characterizations and algorithmic applications of chordal graph embeddings
On interval routing schemes and treewidth
Converting triangulations to quadrangulations
Logical description of context-free graph languages
The complexity of broadcasting in planar and decomposable graphs
Triangulating multitolerance graphs
Farrell polynomials on graphs of bounded tree width
Tree-width and the monadic quantifier hierarchy.
Splitting a graph into disjoint induced paths or cycles.
Channel assignment on graphs of bounded treewidth
The monadic second-order logic of graphs. XII: Planar graphs and planar maps
On minimum cuts and the linear arrangement problem
A comparison of tree transductions defined by monadic second order logic and by attribute grammars
An algorithm for the Tutte polynomials of graphs of bounded treewidth
A comparison of structural CSP decomposition methods
Counting \(H-\)colorings of partial \(k-\)trees
Safe sets in graphs: graph classes and structural parameters
Deleting edges to restrict the size of an epidemic: a new application for treewidth
The multi-stripe travelling salesman problem
Path-contractions, edge deletions and connectivity preservation
Counting linear extensions: parameterizations by treewidth
A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
Algorithm to find a maximum 2-packing set in a cactus
A branch-and-price-and-cut method for computing an optimal bramble
On compatibility and incompatibility of collections of unrooted phylogenetic trees
Complexity of minimum irreducible infeasible subsystem covers for flow networks
A short cut to optimal sequences
Algorithmic meta-theorems for restrictions of treewidth
Two feedback problems for graphs with bounded tree-width
Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
Querying linguistic treebanks with monadic second-order logic in linear time
Parameterized complexity of vertex colouring
A comparison of compatible, finite, and inductive graph properties
The monadic second-order logic of graphs. VIII: Orientations
Reduction algorithms for graphs of small treewidth
The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
On strongly connected digraphs with bounded cycle length
Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
Maximum packing for biconnected outerplanar graphs
Upper bounds to the clique width of graphs
Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
The complexity of finding small separators in temporal graphs
The complexity of frugal colouring
Reducing graph transversals via edge contractions
A unifying model for locally constrained spanning tree problems
Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
Shelah-Stupp's and Muchnik's iterations revisited
New limits of treewidth-based tractability in optimization
Parameterized complexity of \((A,\ell)\)-path packing
Complexity of the multilevel critical node problem
Distance from triviality 2.0: hybrid parameterizations
The tree-width of C
Polynomial kernels for hitting forbidden minors under structural parameterizations
Bounded treewidth as a key to tractability of knowledge representation and reasoning
Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth
Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs
The k-separator problem: polyhedra, complexity and approximation results
Tree-edges deletion problems with bounded diameter obstruction sets
A logical approach to multicut problems
Tree-width and the Sherali-Adams operator
On some domination colorings of graphs
Boundary classes for graph problems involving non-local properties
Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
Hitting forbidden subgraphs in graphs of bounded treewidth
Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
On the satisfiability of quantum circuits of small treewidth
Polynomial-time algorithms for special cases of the maximum confluent flow problem
Complexity and algorithms for recognizing polar and monopolar graphs
Branch decomposition heuristics for linear matroids
Parameterized complexity of firefighting
Algorithms for finding distance-edge-colorings of graphs
Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size
Tree decomposition and discrete optimization problems: a survey
Planar graph bipartization in linear time
Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
A logic of reachable patterns in linked data-structures

This page was built for publication: Easy problems for tree-decomposable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3361904)