Treewidth computations. I: Upper bounds

DOI10.1016/j.ic.2009.03.008zbMath1186.68328OpenAlexW2116793595WikidataQ59567681 ScholiaQ59567681MaRDI QIDQ964001

Hans L. Bodlaender, Arie M. C. A. Koster

Publication date: 14 April 2010

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

Full work available at URL: https://doi.org/10.1016/j.ic.2009.03.008

zbMATH Keywords

upper bounds heuristics treewidth graph algorithms approximation algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings, Finding Good Decompositions for Dynamic Programming on Dense Graphs, Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs, Algorithms and Complexity for Turaev-Viro Invariants, Efficient Problem Solving on Tree Decompositions Using Binary Decision Diagrams, Reduction rules for the maximum parsimony distance on phylogenetic trees, Treewidth distance on phylogenetic trees, Fixed-Parameter Tractability of Treewidth and Pathwidth, Differential geometric treewidth estimation in adiabatic quantum computation, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem, The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing, On quasi-planar graphs: clique-width and logical description, The tree-width of C, Exploiting sparsity for the min \(k\)-partition problem, Lpopt: a rule optimization tool for answer set programming, On the vertex cover \(P_3\) problem parameterized by treewidth, Systematic and deterministic graph minor embedding for Cartesian products of graphs, From tree-decompositions to clique-width terms, Chordal Networks of Polynomial Ideals, Courcelle's theorem -- a game-theoretic approach, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks, Locating Eigenvalues of Symmetric Matrices - A Survey, Branch decomposition heuristics for linear matroids, Turbocharging treewidth heuristics, Practical algorithms for MSO model-checking on tree-decomposable graphs, Exploiting term sparsity in noncommutative polynomial optimization, D-FLAT: Declarative problem solving using tree decompositions and answer-set programming, \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions, Towards fixed-parameter tractable algorithms for abstract argumentation, Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization, A sequential reduction method for inference in generalized linear mixed models, Treewidth computations. II. Lower bounds, Boolean-width of graphs, On the Boolean-Width of a Graph: Structure and Applications, Complexity of secure sets, Variable neighborhood search for graphical model energy minimization, A Local Search Algorithm for Branchwidth, An Experimental Study of the Treewidth of Real-World Graph Data, Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited, Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Treewidth of display graphs: bounds, brambles and applications, Algorithms and complexity for Turaev-Viro invariants, Exploiting sparsity in complex polynomial optimization, Learning tractable Bayesian networks in the space of elimination orders, Evaluating Datalog via tree automata and cycluits, Boolean-Width of Graphs, Tree decompositions and social graphs, Methods for solving reasoning problems in abstract argumentation -- a survey, Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, Customizable Contraction Hierarchies, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness

Uses Software

Cites Work