Treewidth: Algorithmic techniques and results
From MaRDI portal
This is a short survey paper on treewidth. Results and techniques for algorithms that compute the treewidth of a graph are considered. Several algorithms solving difficult problems for graphs with restricted treewidth are also considered. Some results on graph minors are reviewed. For the entire collection see [Zbl 0920.00047].
Recommendations
Cited in
(only showing first 100 items - show all)- Derivation of algorithms for cutwidth and related graph layout parameters
- Edge-maximal graphs of branchwidth k: The k-branches
- Complexity results for minimum sum edge coloring
- The parameterized complexity of the induced matching problem
- AND/OR search spaces for graphical models
- Treewidth. Computations and approximations
- Complexity of list coloring problems with a fixed total number of colors
- Algorithms for graphs with small octopus
- On the extension of a partial metric to a tree metric
- Special issue: Treewidth
- A comparison of structural CSP decomposition methods
- Counting \(H-\)colorings of partial \(k-\)trees
- Listing all potential maximal cliques of a graph
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- The parametrized complexity of knot polynomials
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Exact algorithms for edge domination
- On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines
- A generic convolution algorithm for join operations on tree decompositions
- Eccentricity queries and beyond using hub labels
- Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Backdoors to tractable answer set programming
- Complexity and approximability of extended spanning star forest problems in general and complete graphs
- Obtaining a planar graph by vertex deletion
- Scheduling of pipelined operator graphs
- Polynomial-time algorithms for special cases of the maximum confluent flow problem
- Bandwidth consecutive multicolorings of graphs
- Predecessor existence problems for finite discrete dynamical systems
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Tree decompositions of graphs: saving memory in dynamic programming
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Tree decomposition and discrete optimization problems: a survey
- Boxicity and treewidth
- The relative clique-width of a graph
- Complexity and monotonicity results for domination games
- An algorithmic metatheorem for directed treewidth
- On treewidth approximations
- The algorithmic theory of treewidth
- Triangulating planar graphs while keeping the pathwidth small
- An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification
- Fixed-parameter tractability of treewidth and pathwidth
- On exact algorithms for treewidth
- The complexity status of problems related to sparsest cuts
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs
- Tree Decompositions of Graphs: Saving Memory in Dynamic Programming
- Treewidth and pathwidth parameterized by the vertex cover number
- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
- Treewidth: Characterizations, Applications, and Computations
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- scientific article; zbMATH DE number 1944139 (Why is no real title available?)
- The dag-width of directed graphs
- The complexity of finding uniform sparsest cuts in various graph classes
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- Subexponential parameterized algorithms
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Fast Algorithms for Join Operations on Tree Decompositions
- Threshold Treewidth and Hypertree Width
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- scientific article; zbMATH DE number 7310078 (Why is no real title available?)
- Computational aspects of treewidth for graph
- scientific article; zbMATH DE number 7310159 (Why is no real title available?)
- \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
- Definability in first order theories of graph orderings
- Digraph Decompositions and Monotonicity in Digraph Searching
- Inductive computations on graphs defined by clique-width expressions
- Treewidth: Structure and Algorithms
- A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
- Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems
- SOFSEM 2005: Theory and Practice of Computer Science
- Directed nowhere dense classes of graphs
- Tree-decompositions of small pathwidth
- Tree-decompositions of small pathwidth
- Default logic and bounded treewidth
- Models and solution techniques for frequency assignment problems
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Computing LOGCFL certificates
- Algorithmic uses of the Feferman-Vaught theorem
- Parameterized complexity of minimum membership dominating set
- Augmenting graphs to minimize the radius
- Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
- Digraph decompositions and monotonicity in digraph searching
- Consensus models: computational complexity aspects in modern approaches to the list coloring problem
- Guard games on graphs: keep the intruder out!
- Witnessing subsystems for probabilistic systems with low tree width
- A finite presentation of graphs of treewidth at most three
- Shortest beer path queries based on graph decomposition
- Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)
- Theoretical foundations for parent divorcing transformations in Bayesian networks
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- Treewidth parameterized by feedback vertex number
- Safe separators for treewidth
- Approximation algorithms for treewidth
- Online promise problems with online width metrics
This page was built for publication: Treewidth: Algorithmic techniques and results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4699283)
