Treewidth computations. I: Upper bounds
From MaRDI portal
Publication:964001
DOI10.1016/J.IC.2009.03.008zbMATH Open1186.68328OpenAlexW2116793595WikidataQ59567681 ScholiaQ59567681MaRDI QIDQ964001FDOQ964001
Authors: 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Parallel algorithms in computer science (68W10)
Cites Work
- Title not available (Why is that?)
- Introduction to algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Classes: A Survey
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Graph minors. XIII: The disjoint paths problem
- Incidence matrices and interval graphs
- Parametrized complexity theory.
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Exact Algorithms for Treewidth
- Title not available (Why is that?)
- A sufficiently fast algorithm for finding close to optimal clique trees
- On rigid circuit graphs
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Highly connected sets and the excluded grid theorem
- A comparison of structural CSP decomposition methods
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Representations of chordal graphs as subtrees of a tree
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parallel concepts in graph theory
- Treewidth. Computations and approximations
- Triangulated graphs and the elimination process
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Minimal triangulations of graphs: a survey
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Title not available (Why is that?)
- Algorithmic Aspects of Vertex Elimination on Graphs
- Title not available (Why is that?)
- The Role of Elimination Trees in Sparse Factorization
- The Pathwidth and Treewidth of Cographs
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- The Use of Linear Graphs in Gauss Elimination
- A Separator Theorem for Chordal Graphs
- The elimination form of the inverse and its application to linear programming
- Treewidth: computational experiments
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Title not available (Why is that?)
- Title not available (Why is that?)
- Contraction and Treewidth Lower Bounds
- A characterisation of rigid circuit graphs
- Title not available (Why is that?)
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
- A practical algorithm for making filled graphs minimal
- Maximum cardinality search for computing minimal triangulations of graphs
- Title not available (Why is that?)
- A wide-range algorithm for minimal triangulation from an arbitrary ordering
- Treewidth computations. II. Lower bounds
- A vertex incremental approach for maintaining chordality
- SOFSEM 2005: Theory and Practice of Computer Science
- Graph-Theoretic Concepts in Computer Science
- On treewidth approximations.
- Linear-time computation of optimal subgraphs of decomposable graphs
- Title not available (Why is that?)
- Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
- Title not available (Why is that?)
- The minimum degree heuristic and the minimal triangulation process.
- Minimal orderings revisited
- Heuristic and metaheuristic methods for computing graph treewidth
- Title not available (Why is that?)
- Title not available (Why is that?)
- Solving partial constraint satisfaction problems with tree decomposition
- Lex M versus MCS-M
- Finding good tree decompositions by local search
- Experimental and Efficient Algorithms
Cited In (72)
- Bifurcations in adaptive vascular networks: toward model calibration
- Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited
- Tree-Width for First Order Formulae
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- Locating Eigenvalues of Symmetric Matrices - A Survey
- Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs
- Efficient problem solving on tree decompositions using binary decision diagrams
- An improved spectral lower bound of treewidth
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
- Learning tractable Bayesian networks in the space of elimination orders
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- D-FLAT: declarative problem solving using tree decompositions and answer-set programming
- Turbocharging treewidth heuristics
- Towards fixed-parameter tractable algorithms for abstract argumentation
- Heuristic and metaheuristic methods for computing graph treewidth
- Customizable contraction hierarchies
- Title not available (Why is that?)
- On the vertex cover \(P_3\) problem parameterized by treewidth
- Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
- Treewidth computations. II. Lower bounds
- Special issue: Treewidth
- Courcelle's theorem -- a game-theoretic approach
- Boolean-width of graphs
- A local search algorithm for branchwidth
- A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
- A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
- Experimental and Efficient Algorithms
- Branch decomposition heuristics for linear matroids
- SOFSEM 2005: Theory and Practice of Computer Science
- On the Boolean-width of a graph: structure and applications
- Finding good decompositions for dynamic programming on dense graphs
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- Treewidth distance on phylogenetic trees
- Weighted Treewidth Algorithmic Techniques and Results
- Reduction rules for the maximum parsimony distance on phylogenetic trees
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Boolean-width of graphs
- Complexity of secure sets
- Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth
- Treewidth: Structure and Algorithms
- Title not available (Why is that?)
- From tree-decompositions to clique-width terms
- Differential geometric treewidth estimation in adiabatic quantum computation
- An Experimental Study of the Treewidth of Real-World Graph Data
- Fast Counting with Bounded Treewidth
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
- The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- On quasi-planar graphs: clique-width and logical description
- The tree-width of C
- Exploiting sparsity for the min \(k\)-partition problem
- Variable neighborhood search for graphical model energy minimization
- Treewidth of display graphs: bounds, brambles and applications
- On treewidth approximations.
- Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
- Exploiting term sparsity in noncommutative polynomial optimization
- Exploiting sparsity in complex polynomial optimization
- Evaluating Datalog via tree automata and cycluits
- Tree decompositions and social graphs
- Boxicity and treewidth
- Turbocharging treewidth heuristics
- \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
- A sequential reduction method for inference in generalized linear mixed models
- Computing tree width: from theory to practice and back
- Algorithms and complexity for Turaev-Viro invariants
- Algorithms and complexity for Turaev-Viro invariants
- Jdrasil: a modular library for computing tree decompositions
- Fixed-parameter tractability of treewidth and pathwidth
- Methods for solving reasoning problems in abstract argumentation -- a survey
- Chordal networks of polynomial ideals
- Experimental and Efficient Algorithms
Uses Software
This page was built for publication: Treewidth computations. I: Upper bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q964001)
